{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Title: #Maximum Sum Queries"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Difficulty: #Hard"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Category Title: #Algorithms"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Tag Slug: #stack #binary-indexed-tree #segment-tree #array #binary-search #sorting #monotonic-stack"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Name Translated: #栈 #树状数组 #线段树 #数组 #二分查找 #排序 #单调栈"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solution Name: maximumSumQueries"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Title: #最大和查询"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Content:\n",
    "<p>给你两个长度为 <code>n</code> 、下标从 <strong>0</strong> 开始的整数数组 <code>nums1</code> 和 <code>nums2</code> ，另给你一个下标从 <strong>1</strong> 开始的二维数组 <code>queries</code> ，其中 <code>queries[i] = [x<sub>i</sub>, y<sub>i</sub>]</code> 。</p>\n",
    "\n",
    "<p>对于第 <code>i</code> 个查询，在所有满足 <code>nums1[j] &gt;= x<sub>i</sub></code> 且 <code>nums2[j] &gt;= y<sub>i</sub></code> 的下标 <code>j</code> <code>(0 &lt;= j &lt; n)</code> 中，找出 <code>nums1[j] + nums2[j]</code> 的 <strong>最大值</strong> ，如果不存在满足条件的 <code>j</code> 则返回 <strong>-1</strong> 。</p>\n",
    "\n",
    "<p>返回数组<em> </em><code>answer</code><em> ，</em>其中<em> </em><code>answer[i]</code><em> </em>是第 <code>i</code> 个查询的答案。</p>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>示例 1：</strong></p>\n",
    "\n",
    "<pre><strong>输入：</strong>nums1 = [4,3,1,2], nums2 = [2,4,9,5], queries = [[4,1],[1,3],[2,5]]\n",
    "<strong>输出：</strong>[6,10,7]\n",
    "<strong>解释：</strong>\n",
    "对于第 1 个查询：<code>x<sub>i</sub> = 4</code>&nbsp;且&nbsp;<code>y<sub>i</sub> = 1</code> ，可以选择下标&nbsp;<code>j = 0</code>&nbsp;，此时 <code>nums1[j] &gt;= 4</code>&nbsp;且&nbsp;<code>nums2[j] &gt;= 1</code> 。<code>nums1[j] + nums2[j]</code>&nbsp;等于 6 ，可以证明 6 是可以获得的最大值。\n",
    "对于第 2 个查询：<code>x<sub>i</sub> = 1</code>&nbsp;且&nbsp;<code>y<sub>i</sub> = 3</code> ，可以选择下标&nbsp;<code>j = 2</code>&nbsp;，此时 <code>nums1[j] &gt;= 1</code>&nbsp;且&nbsp;<code>nums2[j] &gt;= 3</code> 。<code>nums1[j] + nums2[j]</code>&nbsp;等于 10 ，可以证明 10 是可以获得的最大值。\n",
    "对于第 3 个查询：<code>x<sub>i</sub> = 2</code>&nbsp;且&nbsp;<code>y<sub>i</sub> = 5</code> ，可以选择下标&nbsp;<code>j = 3</code>&nbsp;，此时 <code>nums1[j] &gt;= 2</code>&nbsp;且&nbsp;<code>nums2[j] &gt;= 5</code> 。<code>nums1[j] + nums2[j]</code>&nbsp;等于 7 ，可以证明 7 是可以获得的最大值。\n",
    "因此，我们返回&nbsp;<code>[6,10,7]</code> 。\n",
    "</pre>\n",
    "\n",
    "<p><strong>示例 2：</strong></p>\n",
    "\n",
    "<pre><strong>输入：</strong>nums1 = [3,2,5], nums2 = [2,3,4], queries = [[4,4],[3,2],[1,1]]\n",
    "<strong>输出：</strong>[9,9,9]\n",
    "<strong>解释：</strong>对于这个示例，我们可以选择下标&nbsp;<code>j = 2</code>&nbsp;，该下标可以满足每个查询的限制。\n",
    "</pre>\n",
    "\n",
    "<p><strong>示例 3：</strong></p>\n",
    "\n",
    "<pre><strong>输入：</strong>nums1 = [2,1], nums2 = [2,3], queries = [[3,3]]\n",
    "<strong>输出：</strong>[-1]\n",
    "<strong>解释：</strong>示例中的查询 <code>x<sub>i</sub></code> = 3 且 <code>y<sub>i</sub></code> = 3 。对于每个下标 j ，都只满足 nums1[j] &lt; <code>x<sub>i</sub></code> 或者 nums2[j] &lt; <code>y<sub>i</sub></code> 。因此，不存在答案。 \n",
    "</pre>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>提示：</strong></p>\n",
    "\n",
    "<ul>\n",
    "\t<li><code>nums1.length == nums2.length</code>&nbsp;</li>\n",
    "\t<li><code>n ==&nbsp;nums1.length&nbsp;</code></li>\n",
    "\t<li><code>1 &lt;= n &lt;= 10<sup>5</sup></code></li>\n",
    "\t<li><code>1 &lt;= nums1[i], nums2[i] &lt;= 10<sup>9</sup>&nbsp;</code></li>\n",
    "\t<li><code>1 &lt;= queries.length &lt;= 10<sup>5</sup></code></li>\n",
    "\t<li><code>queries[i].length ==&nbsp;2</code></li>\n",
    "\t<li><code>x<sub>i</sub>&nbsp;== queries[i][1]</code></li>\n",
    "\t<li><code>y<sub>i</sub> == queries[i][2]</code></li>\n",
    "\t<li><code>1 &lt;= x<sub>i</sub>, y<sub>i</sub> &lt;= 10<sup>9</sup></code></li>\n",
    "</ul>\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Description: [maximum-sum-queries](https://leetcode.cn/problems/maximum-sum-queries/description/)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solutions: [maximum-sum-queries](https://leetcode.cn/problems/maximum-sum-queries/solutions/)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "test_cases = ['[4,3,1,2]\\n[2,4,9,5]\\n[[4,1],[1,3],[2,5]]', '[3,2,5]\\n[2,3,4]\\n[[4,4],[3,2],[1,1]]', '[2,1]\\n[2,3]\\n[[3,3]]']"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from sortedcontainers import SortedDict\n",
    "\n",
    "class Solution:\n",
    "    def maximumSumQueries(self, nums1: List[int], nums2: List[int], queries: List[List[int]]) -> List[int]:\n",
    "        m = len(queries)\n",
    "        s = list(zip(nums1, nums2))\n",
    "        s.sort(reverse=True)\n",
    "        ans = list(range(m))\n",
    "        ans.sort(key = lambda x:queries[x], reverse=True)\n",
    "        \n",
    "        # key 单调递增\n",
    "        # value 单调递增\n",
    "        q = SortedDict()\n",
    "\n",
    "        def add(key, value):\n",
    "            key = -key\n",
    "            index = q.bisect_left(key)\n",
    "            # print(key, value, index, q, \"add\")\n",
    "            while index < len(q) and q.peekitem(index)[1] <= value and q.peekitem(index)[0] >= key:\n",
    "                q.popitem(index)[0]\n",
    "            # print(key, value, index, q, \"add1\")\n",
    "            if q and q.peekitem(0)[1] >= value and q.peekitem(0)[0] <= key:\n",
    "                return\n",
    "            # while q and q.peekitem(0)\n",
    "            q[key] = value\n",
    "            # print(key, value, index, q, \"add_after\")\n",
    "            # print(key, value, q)\n",
    "\n",
    "        def find(key, i):\n",
    "            key = -key\n",
    "            index = q.bisect_right(key)\n",
    "            # print(q, index, key, i, \"find\")\n",
    "            if index == 0:\n",
    "                return -1\n",
    "            return q.peekitem(index - 1)[1]\n",
    "\n",
    "        n = len(s)\n",
    "        j = 0\n",
    "        for i in ans:\n",
    "            qa, qb = queries[i]\n",
    "            while j < n and s[j][0] >= qa:\n",
    "                add(s[j][1], s[j][0] + s[j][1])\n",
    "                j += 1\n",
    "            \n",
    "            queries[i] = find(qb, i)\n",
    "\n",
    "        return queries\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maximumSumQueries(self, nums1: List[int], nums2: List[int], queries: List[List[int]]) -> List[int]:\n",
    "        rec = [(a, b) for a, b in zip(nums1, nums2)]\n",
    "        rec.sort()\n",
    "        stk = []\n",
    "        for i in range(len(queries)):\n",
    "            queries[i].append(i)\n",
    "        queries.sort()\n",
    "        res = [-1 for _ in range(len(queries))]\n",
    "        while queries:\n",
    "            t = queries.pop()\n",
    "            while rec and rec[-1][0] >= t[0]:\n",
    "                tv = rec.pop()\n",
    "                n = (tv[1], tv[0] + tv[1])\n",
    "                while stk and stk[-1][1] <= n[1]:\n",
    "                    stk.pop()\n",
    "                if not stk or stk[-1][0] < n[0]:\n",
    "                    stk.append(n)\n",
    "            i = bisect.bisect_left(stk, (t[1], 0))\n",
    "            if i < len(stk) and stk[i][1] >= t[0]:\n",
    "                res[t[2]] = stk[i][1]\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maximumSumQueries(\n",
    "        self, nums1: List[int], nums2: List[int], qu: List[List[int]]\n",
    "    ) -> List[int]:\n",
    "        rec = [(a, b) for a, b in zip(nums1, nums2)]\n",
    "        rec.sort()\n",
    "        stk = []\n",
    "        for i in range(len(qu)):\n",
    "            qu[i].append(i)\n",
    "        qu.sort()\n",
    "        res = [-1 for _ in range(len(qu))]\n",
    "        while qu:\n",
    "            t = qu.pop()\n",
    "            while rec and rec[-1][0] >= t[0]:\n",
    "                tv = rec.pop()\n",
    "                n = (tv[1], tv[0] + tv[1])\n",
    "                while stk and stk[-1][1] <= n[1]:\n",
    "                    stk.pop()\n",
    "                if not stk or stk[-1][0] < n[0]:\n",
    "                    stk.append(n)\n",
    "            i = bisect.bisect_left(stk, (t[1], 0))\n",
    "            if i < len(stk) and stk[i][1] >= t[0]:\n",
    "                res[t[2]] = stk[i][1]\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maximumSumQueries(self, nums1: List[int], nums2: List[int], qu: List[List[int]]) -> List[int]:\n",
    "        rec = [(a, b) for a, b in zip(nums1, nums2)]\n",
    "        rec.sort()\n",
    "        stk = []\n",
    "        for i in range(len(qu)):\n",
    "            qu[i].append(i)\n",
    "        qu.sort()\n",
    "        res = [-1 for _ in range(len(qu))]\n",
    "        while qu:\n",
    "            t = qu.pop()\n",
    "            while rec and rec[-1][0] >= t[0]:\n",
    "                tv = rec.pop()\n",
    "                n = (tv[1], tv[0] + tv[1])\n",
    "                while stk and stk[-1][1] <= n[1]:\n",
    "                    stk.pop()\n",
    "                if not stk or stk[-1][0] < n[0]:\n",
    "                    stk.append(n)\n",
    "            i = bisect.bisect_left(stk, (t[1], 0))\n",
    "            if i < len(stk) and stk[i][1] >= t[0]:\n",
    "                res[t[2]] = stk[i][1]\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "   def maximumSumQueries(self, nums1: List[int], nums2: List[int], queries: List[List[int]]) -> List[int]:\n",
    "       n,m=len(nums1),len(queries);ans,stk=[0]*m,[]\n",
    "       num1=sorted([(nums1[i],nums2[i]) for i in range(n)])\n",
    "       for i in range(n):\n",
    "           while(len(stk) and stk[-1][1]<=num1[i][1]):del stk[-1]\n",
    "           stk.append(num1[i])\n",
    "       t=len(stk);q=int(math.log2(t))+1;f=[[0]*q for i in range(t)]\n",
    "       num2,num3=[stk[i][0] for i in range(t)],[stk[t-i-1][1] for i in range(t)]\n",
    "       mp={i:1<<i for i in range(q)}\n",
    "       for i in range(t):f[i][0]=stk[i][0]+stk[i][1]\n",
    "       for i in range(1,q):\n",
    "           x,y=mp[i-1],t-mp[i]\n",
    "           for j in range(y+1):f[j][i]=max(f[j][i-1],f[j+x][i-1])\n",
    "       for i in range(m):\n",
    "           x,y=bisect_left(num2,queries[i][0]),t-bisect_left(num3,queries[i][1])-1\n",
    "           if(y<x):ans[i]=-1\n",
    "           elif(x==y):ans[i]=f[x][0]\n",
    "           else:z=int(math.log2(y-x));ans[i]=max(f[x][z],f[y-mp[z]+1][z])\n",
    "       return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maximumSumQueries(self, nums1: List[int], nums2: List[int], queries: List[List[int]]) -> List[int]:\n",
    "        sums = sorted([(a+b,a,b) for a,b in zip(nums1,nums2)],reverse=True)\n",
    "        @functools.lru_cache()\n",
    "        def query(q1,q2):\n",
    "            for s,n1,n2 in sums:\n",
    "                if s < q1+q2:               return(-1)\n",
    "                if n1 >= q1 and n2 >= q2:   return(s)\n",
    "            return(-1)        \n",
    "        return([query(q1,q2) for q1,q2 in queries]) \n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maximumSumQueries(self, nums1: List[int], nums2: List[int], queries: List[List[int]]) -> List[int]:\n",
    "        n, m = len(nums1), len(queries)\n",
    "        arr = sorted([(x1, x2) for x1, x2 in zip(nums1, nums2)], key=lambda x: -x[0])\n",
    "        qid = sorted([i for i in range(m)], key=lambda x: -queries[x][0])\n",
    "        ans = [0] * m\n",
    "        stk = []\n",
    "        j = 0\n",
    "        for i in qid:\n",
    "            x, y = queries[i][0], queries[i][1]\n",
    "            while j < n and arr[j][0] >= x:\n",
    "                while stk and stk[-1][1] <= arr[j][0] + arr[j][1]:\n",
    "                    stk.pop()\n",
    "                if not stk or stk[-1][0] < arr[j][1]:\n",
    "                    stk.append((arr[j][1], arr[j][0] + arr[j][1]))\n",
    "                j += 1\n",
    "            idx = bisect_left(stk, y, key=lambda x:x[0])\n",
    "            ans[i] = stk[idx][1] if idx < len(stk) else -1\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maximumSumQueries(self, nums1: List[int], nums2: List[int], queries: List[List[int]]) -> List[int]:\n",
    "        #超时暴力\n",
    "        # answer = []\n",
    "        # for i in range(len(queries)):\n",
    "        #     maxsum = -1\n",
    "        #     for j in range(len(nums1)):\n",
    "        #         if nums1[j] >= queries[i][0] and nums2[j] >= queries[i][1]:\n",
    "        #             maxsum = max(maxsum, nums1[j] + nums2[j])\n",
    "\n",
    "        #     answer.append(maxsum)\n",
    "        # return answer\n",
    "        \n",
    "        sums = sorted([(a+b,a,b) for a,b in zip(nums1,nums2)], key=lambda x: x[0], reverse=True)\n",
    "        @functools.lru_cache() #用来记录已经算过一次的结果\n",
    "        def query(q1, q2):\n",
    "            for s, n1, n2 in sums:\n",
    "                if s < q1+q2:\n",
    "                    return -1\n",
    "                if n1>= q1 and n2 >= q2:\n",
    "                    return s\n",
    "            return -1\n",
    "        return [query(q1,q2) for q1, q2 in queries]\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maximumSumQueries(self, nums1: List[int], nums2: List[int], queries: List[List[int]]) -> List[int]:\n",
    "        nums=[]\n",
    "        for i in range(len(nums1)):\n",
    "            nums.append((nums1[i],nums2[i]))\n",
    "        nums.sort(key=lambda x:(x[0],x[1]))\n",
    "        stack=[(0,10**9+1)]\n",
    "        for i in range(len(nums)):\n",
    "            while stack!=[] and stack[-1][0]<=nums[i][0] and stack[-1][1]<=nums[i][1]:\n",
    "                stack.pop()\n",
    "            stack.append(nums[i])\n",
    "        stack.append((10**9+1,0))\n",
    "        tree=[0]*4*(len(stack)-2)\n",
    "        def build(n,left,right,i):\n",
    "            if left+1==right:\n",
    "                tree[n]=sum(stack[i])\n",
    "                return tree[n]\n",
    "            mid=(left+right)//2\n",
    "            if left<=i<mid:\n",
    "                build(2*n+1,left,mid,i)\n",
    "            else:\n",
    "                build(2*n+2,mid,right,i)\n",
    "            tree[n]=max(tree[2*n+1],tree[2*n+2])\n",
    "            return tree[n]\n",
    "        for i in range(1,len(stack)-1):\n",
    "            build(0,1,len(stack)-1,i)\n",
    "        def find(n,left,right,ql,qr):\n",
    "            if ql>=qr:\n",
    "                return -1\n",
    "            if ql==left and qr==right:\n",
    "                return tree[n]\n",
    "            mid=(left+right)//2\n",
    "            if ql>=mid:\n",
    "                return find(2*n+2,mid,right,ql,qr)\n",
    "            elif qr<=mid:\n",
    "                return find(2*n+1,left,mid,ql,qr)\n",
    "            else:\n",
    "                return max(find(2*n+1,left,mid,ql,mid),find(2*n+2,mid,right,mid,qr))\n",
    "        def getleft(x):\n",
    "            l,r=0,len(stack)\n",
    "            while r-l>1:\n",
    "                m=(r+l)//2\n",
    "                if stack[m][0]<x:\n",
    "                    l=m\n",
    "                else:\n",
    "                    r=m\n",
    "            return r\n",
    "        def getright(x):\n",
    "            l,r=0,len(stack)\n",
    "            while r-l>1:\n",
    "                m=(r+l)//2\n",
    "                if stack[m][1]>=x:\n",
    "                    l=m\n",
    "                else:\n",
    "                    r=m\n",
    "            return r\n",
    "        ans=[]\n",
    "        for i in queries:\n",
    "            ans.append(find(0,1,len(stack)-1,getleft(i[0]),getright(i[1])))\n",
    "        return ans\n",
    "\n",
    "\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# 要按照index来 不能排序\n",
    "# 说白了有n对 每次查询都是在这n对里面找最优解\n",
    "# 要是x1 > x2 且 y1 > y2 那么x2,y2就废了\n",
    "# 将nums1 nums2绑在一起就可以了 解决了index\n",
    "# 将n1进行升序排序 那么n1确定的范围可以通过二分确认\n",
    "# n1升序 那么开多一个降序单调栈 淘汰那些被完爆的 单调栈里面的元素就是可能被选的\n",
    "# 根据单调栈元素 重新生成nums1 nums2 用两次二分确定左右区间\n",
    "# 1 2 3 4 index1 4321 index2\n",
    "class Solution:\n",
    "    def maximumSumQueries(self, nums1: List[int], nums2: List[int], queries: List[List[int]]) -> List[int]:\n",
    "        nums = [[i, j] for i, j in zip(nums1, nums2)]\n",
    "        nums.sort(key=lambda x: (x[0], -x[1]))\n",
    "        stack = []\n",
    "        for i, (_, j) in enumerate(nums):\n",
    "            while stack and j >= nums[stack[-1]][1]:\n",
    "                stack.pop()\n",
    "            stack.append(i)\n",
    "        # nums2逆序方便用bisect\n",
    "        nums1, nums2 = [nums[i][0] for i in stack], [nums[i][1] for i in stack[::-1]]\n",
    "        res = []\n",
    "        for i, j in queries:\n",
    "            left = bisect_left(nums1, i)\n",
    "            right = len(nums2) - bisect_left(nums2, j)\n",
    "            res.append(max(nums1[i] + nums2[-1 - i] for i in range(left, right)) if right > left else -1)\n",
    "        return res\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# https://leetcode.cn/u/l00/\n",
    "\n",
    "# https://leetcode.cn/problems/maximum-sum-queries/solution/tu-wen-xiang-jie-chi-xian-pai-xu-he-jing-0ncw/\n",
    "\n",
    "class Solution:\n",
    "    def maximumSumQueries(self, nums1: List[int], nums2: List[int], queries: List[List[int]]) -> List[int]:\n",
    "        n = len(nums1)\n",
    "        numsS = [num1 + num2 for num1, num2 in zip(nums1, nums2)]\n",
    "        sortByX = sorted(range(n), key=lambda it:nums1[it])\n",
    "        sortByY = sorted(range(n), key=lambda it:nums2[it])\n",
    "        xSortIndex = [-1] * n\n",
    "        for i, num in enumerate(sortByX): xSortIndex[num] = i\n",
    "        # rightByY = sortByY.copy()[nums1[idx] for idx in sortByY]\n",
    "        # for i in range(n - 2, -1, -1): rightByY[i] = max(rightByY[i], rightByY[i + 1])\n",
    "        rightByY = sortByY.copy()\n",
    "        for i in range(n - 2, -1, -1):\n",
    "            if nums1[rightByY[i]] <= nums1[rightByY[i + 1]]:\n",
    "                rightByY[i] = rightByY[i + 1]\n",
    "        \n",
    "        print(\"numsS\",numsS)\n",
    "        print(\"sortByX\",sortByX)\n",
    "        print(\"sortByY\",sortByY)\n",
    "        print(\"rightByY\",rightByY)\n",
    "\n",
    "        sidx = n + (n & 1)\n",
    "        tree = ([-1] * sidx) + sortByX\n",
    "        # print(\"tree\",tree)\n",
    "\n",
    "        for i in range(len(tree) - 1, 1, -1):\n",
    "            p = i >> 1\n",
    "            if tree[p] == -1 or numsS[tree[p]] < numsS[tree[i]]: tree[p] = tree[i]\n",
    "        \n",
    "        print(\"tree\",tree)\n",
    "\n",
    "        def TreeQuery(idx: int, curLeft: int, curRight: int, targetLeft: int, targetRight: int) -> int:\n",
    "            # if idx >= len(tree): return -1\n",
    "            # if curRight < targetLeft or targetRight < curLeft: return -1\n",
    "            # if targetLeft <= curLeft and curRight <= targetRight:\n",
    "            #     return numsS[tree[idx]]\n",
    "            \n",
    "            # mid = (curLeft + curRight) >> 1\n",
    "            # return max(TreeQuery(idx << 1, curLeft, mid, targetLeft, targetRight), TreeQuery(idx << 1 | 1, mid + 1, curRight, targetLeft, targetRight))\n",
    "            left = sidx + targetLeft\n",
    "            right = sidx + targetRight\n",
    "            leftRes = numsS[tree[left]]\n",
    "            rightRes = numsS[tree[right]]\n",
    "            # print(\"TreeQuery\",\"left\",left,\"right\",right)\n",
    "            \n",
    "            # ans = -1\n",
    "            # while left < right:\n",
    "            #     print(left, right)\n",
    "            #     if right & 1 == 0: right -= 1\n",
    "            #     right >>= 1\n",
    "            #     rightRes = max(rightRes, numsS[tree[right]])\n",
    "            #     if left > right:\n",
    "            #         if left & 1 == 1: left += 1\n",
    "            #         left >>= 1\n",
    "            #         leftRes = max(leftRes, numsS[tree[left]])\n",
    "            # return max(leftRes, rightRes)\n",
    "            ans = -1\n",
    "            while left < right:\n",
    "                # print(left, right)\n",
    "                rightRes = max(rightRes, numsS[tree[right]])\n",
    "                if right & 1 == 0: right -= 1\n",
    "                right >>= 1\n",
    "                leftRes = max(leftRes, numsS[tree[left]])\n",
    "                if left & 1 == 1: left += 1\n",
    "                left >>= 1\n",
    "            if left == right: leftRes = max(leftRes, numsS[tree[left]])\n",
    "                    \n",
    "            return max(leftRes, rightRes)\n",
    "                \n",
    "                \n",
    "\n",
    "\n",
    "            \n",
    "\n",
    "        ans = []\n",
    "        for qX, qY in queries:\n",
    "            curY = bisect_left(sortByY, qY, key=lambda it:nums2[it])\n",
    "            \n",
    "            # print(curY)\n",
    "            if curY < n:\n",
    "                left = bisect_left(sortByX, qX, key=lambda it:nums1[it])\n",
    "                right = xSortIndex[rightByY[curY]]\n",
    "                # print(\"left\",left,\"right\",right)\n",
    "                if left <= right:\n",
    "                    res = TreeQuery(1, 0, n - 1, left, right)\n",
    "                    print(\"res\",res)\n",
    "                    ans.append(res)\n",
    "                    continue\n",
    "                \n",
    "            ans.append(-1)\n",
    "            \n",
    "        \n",
    "        return ans\n",
    "\n",
    "        \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maximumSumQueries(self, nums1: List[int], nums2: List[int], queries: List[List[int]]) -> List[int]:\n",
    "        ans = [-1] * len(queries)\n",
    "        sums = sorted(((a, b) for a, b in zip(nums1, nums2)), key=lambda e: e[0], reverse=True)\n",
    "        j, st = 0, []\n",
    "        for i, (x, y) in sorted(enumerate(queries), key=lambda e: e[1][0], reverse=True):\n",
    "            while j < len(sums) and sums[j][0] >= x:\n",
    "                ax, ay = sums[j]\n",
    "                while st and st[-1][1] <= ax + ay: st.pop()\n",
    "                if not st or st[-1][0] < ay: st.append((ay, ax + ay))\n",
    "                j += 1\n",
    "            p = bisect_left(st, (y,))\n",
    "            if p < len(st): ans[i] = st[p][1]\n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maximumSumQueries(self, nums1: List[int], nums2: List[int], queries: List[List[int]]) -> List[int]:\n",
    "        comba=sorted(zip(nums1,nums2),reverse=True)\n",
    "        ans=[-1]*len(queries)\n",
    "        stack=[]\n",
    "        j=0\n",
    "        for i,[x,y] in sorted(enumerate(queries),key=lambda p:p[1][0],reverse=True):\n",
    "            while j<len(nums1) and comba[j][0]>=x:\n",
    "                x1,y1=comba[j]\n",
    "                while stack and stack[-1][1]<x1+y1:\n",
    "                    stack.pop()\n",
    "                if not stack or y1>stack[-1][0]:\n",
    "                    stack.append([y1, x1 + y1])\n",
    "                j+=1\n",
    "            a=bisect_left(stack,[y,])\n",
    "            if a<len(stack):\n",
    "                ans[i]=stack[a][1]\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from typing import List\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    def maximumSumQueries(self, nums1: List[int], nums2: List[int], queries: List[List[int]]) -> List[int]:\n",
    "        q = []\n",
    "        m, n = len(queries), len(nums1)\n",
    "        for i,(x,y) in enumerate(queries):\n",
    "            q.append((x, y, i))\n",
    "        q.sort(key=lambda x: (-x[0]))\n",
    "\n",
    "        ans = [-1] * m\n",
    "        a = []\n",
    "        for x, y in zip(nums1, nums2):\n",
    "            a.append((x, y))\n",
    "\n",
    "        a.sort(key=lambda x: -x[0])\n",
    "\n",
    "        # print(q, a)\n",
    "\n",
    "        i,j = 0,0\n",
    "        stack = []\n",
    "        while(i < m):\n",
    "            x,y,w = q[i]\n",
    "            while(j < n and a[j][0] >= x):\n",
    "                while(stack and ((sum(a[j]) > stack[-1][0]) or (sum(a[j]) == stack[-1][0] and a[j][1] > stack[-1][1]))):\n",
    "                    stack.pop()\n",
    "                if(not stack or a[j][1] > stack[-1][1]):\n",
    "                    stack.append((sum(a[j]), a[j][1]))\n",
    "                j += 1\n",
    "\n",
    "            # print(\"stack\", stack, y)\n",
    "\n",
    "            if(stack):\n",
    "                left,right = 0,len(stack)-1\n",
    "                while(left<=right):\n",
    "                    mid=(left+right) // 2\n",
    "                    if(stack[mid][1] >= y):\n",
    "                        right = mid - 1\n",
    "                    else:\n",
    "                        left = mid + 1\n",
    "                if(left < len(stack)):\n",
    "                    ans[w] = stack[left][0]\n",
    "            i += 1\n",
    "\n",
    "\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maximumSumQueries(self, nums1: List[int], nums2: List[int], queries: List[List[int]]) -> List[int]:\n",
    "        \n",
    "        def insert(begin, end, pos, val):\n",
    "            mid = (begin + end) >> 1\n",
    "            b[mid] = max(b[mid], val)\n",
    "            if mid == pos:\n",
    "                a[mid] = max(a[mid], val)\n",
    "            elif pos < mid:\n",
    "                insert(begin, mid-1, pos, val)\n",
    "            else:\n",
    "                insert(mid+1, end, pos, val)\n",
    "        \n",
    "        def query(begin, end, l):\n",
    "            mid = (begin + end) >> 1\n",
    "            if l <= begin:\n",
    "                return b[mid]\n",
    "            if l > mid:\n",
    "                return query(mid+1, end, l)\n",
    "            res = max(a[mid], query(mid+1, end, l))\n",
    "            if l < mid:\n",
    "                res = max(res, query(begin, mid-1, l))\n",
    "            return res\n",
    "        \n",
    "        m = len(nums1)\n",
    "        n = len(queries)\n",
    "        tot = [x + y for x,y in zip(nums1, nums2)]\n",
    "        s = set(nums2)\n",
    "        for x,y in queries:\n",
    "            s.add(y)\n",
    "        l = sorted(list(s))\n",
    "        M = len(l)\n",
    "        a = [-1] * M\n",
    "        b = [-1] * M\n",
    "        mp = {}\n",
    "        for i,val in enumerate(l):\n",
    "            mp[val] = i\n",
    "        for i,val in enumerate(nums2):\n",
    "            nums2[i] = mp[val]\n",
    "        for i, (x,y) in enumerate(queries):\n",
    "            queries[i][1] = mp[y]\n",
    "        idx = sorted(range(m), key=lambda x: nums1[x], reverse=1)\n",
    "        idx2 = sorted(range(n), key=lambda x: queries[x][0], reverse=1)\n",
    "        res = [-1] * n\n",
    "        pos = 0\n",
    "        for k in idx2:\n",
    "            x, y = queries[k]\n",
    "            while pos < m and nums1[idx[pos]] >= x:\n",
    "                insert(0, M-1, nums2[idx[pos]], tot[idx[pos]])\n",
    "                pos += 1\n",
    "            res[k] = query(0, M-1, y)\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maximumSumQueries(self, nums1: List[int], nums2: List[int], queries: List[List[int]]) -> List[int]:\n",
    "        queries_idx = [(x, y, idx) for idx, (x, y) in enumerate(queries)]\n",
    "        queries_idx.sort(key=lambda x: -x[0])\n",
    "        nums = [(x,y) for x,y in zip(nums1, nums2)]\n",
    "        nums.sort(key=lambda x: -x[0])\n",
    "        # 现在我有两个序列，都是按照x排好序了，\n",
    "        nq = len(queries)\n",
    "        nn = len(nums)\n",
    "        ans = [-1] * nq\n",
    "        # 较小的y对应更大的 x + y，因为可选择的余地大\n",
    "        stack = []\n",
    "        i = 0\n",
    "        # 按x从大到小遍历queries\n",
    "        for x, y, idx in queries_idx:\n",
    "            # 按x从大到小寻找符合x条件的点\n",
    "            while i < nn and  nums[i][0] >= x:\n",
    "                nx, ny = nums[i]\n",
    "                total = nx + ny\n",
    "                # x_new <= x_visited\n",
    "                # if y_new <= all(y_visited), ignore this case\n",
    "                # if y_new > any(y_visited), it is possible to update stack\n",
    "                while stack and stack[-1][1] <= total:\n",
    "                    stack.pop()\n",
    "                if not stack or stack[-1][0] < ny:\n",
    "                    stack.append((ny, total))\n",
    "                i += 1\n",
    "            k = bisect_left(stack, (y, 0))\n",
    "            if k < len(stack):\n",
    "                ans[idx] = stack[k][1]\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def query(self, tree: List[int], ind: int, left: int, right: int, x: int, y: int) -> int:\n",
    "        if left >= x and right <= y:\n",
    "            return tree[ind]\n",
    "        mid = (left + right) >> 1\n",
    "        r = -1\n",
    "        if x <= mid:\n",
    "            r = self.query(tree, ind << 1, left, mid, x, y)\n",
    "        if y > mid:\n",
    "            r = max(r, self.query(tree, (ind << 1) | 1, mid + 1, right, x, y))\n",
    "        return r\n",
    "\n",
    "    def update(self, tree: List[int], ind: int, left: int, right: int, x: int, y: int) -> None:\n",
    "        tree[ind] = max(tree[ind], y)\n",
    "        if left >= x and right <= x:\n",
    "            return\n",
    "        mid = (left + right) >> 1\n",
    "        if x <= mid:\n",
    "            self.update(tree, ind << 1, left, mid, x, y)\n",
    "        else:\n",
    "            self.update(tree, (ind << 1) | 1, mid + 1, right, x, y)\n",
    "\n",
    "    def maximumSumQueries(self, nums1: List[int], nums2: List[int], queries: List[List[int]]) -> List[int]:\n",
    "        n = len(nums1)\n",
    "        all_nums = defaultdict(int)\n",
    "        v = [(nums1[i], nums2[i]) for i in range(n)]\n",
    "        for num in nums2:\n",
    "            all_nums[num] += 1\n",
    "        v.sort()\n",
    "        m = len(queries)\n",
    "        ind = [i for i in range(m)]\n",
    "        for query in queries:\n",
    "            all_nums[query[1]] += 1\n",
    "        ind.sort(key=lambda x: queries[x][0], reverse=True)\n",
    "        mv = 0\n",
    "        for key in sorted(all_nums.keys()):\n",
    "            mv += 1\n",
    "            all_nums[key] = mv\n",
    "        tree = [-1] * (mv << 2)\n",
    "        r = [0] * m\n",
    "        j = n - 1\n",
    "        for i in ind:\n",
    "            while j >= 0 and v[j][0] >= queries[i][0]:\n",
    "                self.update(tree, 1, 1, mv, all_nums[v[j][1]], v[j][0] + v[j][1])\n",
    "                j -= 1\n",
    "            r[i] = self.query(tree, 1, 1, mv, all_nums[queries[i][1]], mv)\n",
    "        return r"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maximumSumQueries(self, nums1: List[int], nums2: List[int], queries: List[List[int]]) -> List[int]:\n",
    "        merge_boundary_list, boundary_sum = self.merge_boundary(nums1, nums2)\n",
    "        res = [0] * len(queries)\n",
    "        awser_dict = {}\n",
    "        for qur_index, quer in enumerate(queries):\n",
    "            if tuple(quer) in awser_dict:\n",
    "                res[qur_index] = awser_dict[tuple(quer)]\n",
    "                continue\n",
    "            max_sum = -1\n",
    "            for cur_index in range(len(merge_boundary_list)):\n",
    "                if merge_boundary_list[cur_index][0] - quer[0] >= 0 and merge_boundary_list[cur_index][1] - quer[\n",
    "                    1] >= 0 and boundary_sum[cur_index] > max_sum:\n",
    "                    max_sum = boundary_sum[cur_index]\n",
    "            res[qur_index] = max_sum\n",
    "            awser_dict[tuple(quer)] = max_sum\n",
    "        return res\n",
    "    \n",
    "    def merge_boundary(self, tar_nums1, tar_nums2):\n",
    "        merge_boundary_list = [[tar_nums1[0], tar_nums2[0]]]\n",
    "        sum_list = [tar_nums1[0] + tar_nums2[0]]\n",
    "        for index in range(0, len(tar_nums1)):\n",
    "            cur_merge = [tar_nums1[index], tar_nums2[index]]\n",
    "            if cur_merge in merge_boundary_list:\n",
    "                continue\n",
    "            has_match = False\n",
    "            for cur_merge_index in range(len(merge_boundary_list)):\n",
    "                if cur_merge[0] - merge_boundary_list[cur_merge_index][0] >= 0 and \\\n",
    "                    cur_merge[1] - merge_boundary_list[cur_merge_index][1] >= 0:\n",
    "                    merge_boundary_list[cur_merge_index][0] = cur_merge[0]\n",
    "                    merge_boundary_list[cur_merge_index][1] = cur_merge[1]\n",
    "                    sum_list[cur_merge_index] = cur_merge[0] + cur_merge[1]\n",
    "                    has_match = True\n",
    "                    break\n",
    "                elif cur_merge[0] - merge_boundary_list[cur_merge_index][0] <= 0 and \\\n",
    "                    cur_merge[1] - merge_boundary_list[cur_merge_index][1] <= 0:\n",
    "                    has_match = True\n",
    "                    break\n",
    "            if not has_match:\n",
    "                merge_boundary_list.append(cur_merge)\n",
    "                sum_list.append(cur_merge[0] + cur_merge[1])\n",
    "        return merge_boundary_list, sum_list"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from typing import List\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    def maximumSumQueries(self, nums1: List[int], nums2: List[int], queries: List[List[int]]) -> List[int]:\n",
    "        a = sorted(zip(range(len(queries)), queries), key=lambda t: -t[1][0])\n",
    "        b = sorted(([x, y] for x, y in zip(nums1, nums2)), key=lambda t: -t[0])\n",
    "        ans = [-1] * len(queries)\n",
    "        i = 0\n",
    "        n = len(b)\n",
    "        st = []\n",
    "        for idx, q in a:\n",
    "            while i < n and q[0] <= b[i][0]:\n",
    "                x, y = b[i]\n",
    "                while st and x + y >= st[-1][1]:\n",
    "                    st.pop()\n",
    "                if not st or y > st[-1][0]:\n",
    "                    st.append([y, x + y])\n",
    "                i += 1\n",
    "            j = bisect_left(st, [q[1], 0])\n",
    "            if j < len(st):\n",
    "                ans[idx] = st[j][1]\n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from typing import List\n",
    "from bisect import bisect_left\n",
    "\n",
    "class Solution:\n",
    "  def maximumSumQueries(self, nums1: List[int], nums2: List[int], queries: List[List[int]]) -> List[int]:\n",
    "    nums = sorted(zip(nums1, nums2), reverse=True)\n",
    "    n = len(nums)\n",
    "    q = sorted(enumerate(queries), key=lambda x: -x[1][0])\n",
    "    ans = [-1] * len(q)\n",
    "    i = 0\n",
    "    stack = []\n",
    "    for qi, (x, y) in q:\n",
    "      while i < n and nums[i][0] >= x:\n",
    "        n1, n2 = nums[i]\n",
    "        s = n1 + n2\n",
    "        # if stack and n2 <= stack[-1][0]: continue\n",
    "        # n2 > s[-1][0]\n",
    "        while stack and s >= stack[-1][1]:\n",
    "          stack.pop()\n",
    "        # s < stack[-1][1]\n",
    "        if not stack or n2 > stack[-1][0]:\n",
    "          stack.append((n2, s))\n",
    "        i += 1\n",
    "      j = bisect_left(stack, (y, 0))\n",
    "      if j < len(stack): ans[qi] = stack[j][1]\n",
    "    return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class BIT:\n",
    "    def __init__(self, n):\n",
    "        self.tree = [-1]*n \n",
    "        self.n = n \n",
    "    \n",
    "    def update(self, i, mx):\n",
    "        while i:\n",
    "            self.tree[i] = max(mx, self.tree[i])\n",
    "            i -= i&-i \n",
    "    \n",
    "    def query(self, i):\n",
    "        res = -1\n",
    "        while i<self.n:\n",
    "            res = max(res, self.tree[i])\n",
    "            i += i&-i \n",
    "        return res\n",
    "\n",
    "class Solution:\n",
    "    def maximumSumQueries(self, nums1: List[int], nums2: List[int], queries: List[List[int]]) -> List[int]:\n",
    "        n = len(nums1)\n",
    "        a = [(x, y, x + y) for x, y in zip(nums1, nums2)]\n",
    "        a.sort()\n",
    "        tree = BIT(n + 1)\n",
    "        qs = [(x, y, i) for i, (x, y) in enumerate(queries)]\n",
    "        qs.sort(reverse=True)\n",
    "        b = sorted(set(nums2))\n",
    "        i = n - 1\n",
    "        res = [-1] * len(queries)\n",
    "        for x, y, qi in qs:\n",
    "            # j = bisect_left(a, [x, -1, -1])\n",
    "            # if j == n:\n",
    "            #     continue\n",
    "            while i >= 0 and a[i][0] >= x:\n",
    "                tree.update(bisect_left(b, a[i][1]) + 1, a[i][2])\n",
    "                i -= 1\n",
    "            res[qi] = tree.query(bisect_left(b, y) + 1)\n",
    "        return res\n",
    "\n",
    "        # res = [-1] * len(queries)\n",
    "        # a = sorted(((x, y) for x, y in zip(nums1, nums2)), key=lambda p: -p[0])\n",
    "        # qs = sorted([(i, x, y) for i, (x, y) in enumerate(queries)], key=lambda x: -x[1])\n",
    "        # j = 0\n",
    "        # stk = [] #存(ay, ax + ay), ay递增，ax+ay递减\n",
    "        # for i, x, y in qs:\n",
    "        #     while j < len(a) and a[j][0] >= x:\n",
    "        #         ax, ay = a[j]\n",
    "        #         while stk and stk[-1][1] <= ax + ay:\n",
    "        #             stk.pop()\n",
    "        #         if not stk or stk[-1][0] < ay:\n",
    "        #             stk.append((ay, ax + ay))\n",
    "        #         j += 1\n",
    "        #     p = bisect_left(stk, (y,))\n",
    "        #     if p < len(stk):\n",
    "        #         res[i] = stk[p][1]\n",
    "        # return res\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maximumSumQueries(self, nums1: List[int], nums2: List[int], queries: List[List[int]]) -> List[int]:\n",
    "        # 数字查询双逆序排序+单调栈存递增y递减sm+二分查找y\n",
    "        tuples = sorted(zip(nums1, nums2))[::-1]\n",
    "        q = sorted([x, y, i] for (i, [x, y]) in enumerate(queries))[::-1]\n",
    "        res = [-1] * len(queries)\n",
    "        j = 0\n",
    "        # 元组单调栈存[num2,num1+num2]\n",
    "        stack = []\n",
    "        for x, y, i in q:\n",
    "            while j < len(tuples) and tuples[j][0] >= x:\n",
    "                num1, num2 = tuples[j]\n",
    "                while stack and stack[-1][1] <= num1 + num2:\n",
    "                    # 栈顶元素的num2虽然大, 但总和小, 也就是num2小\n",
    "                    # 而当前query不需要那么大的num1了, 只需要更大的num2和sm\n",
    "                    # 所以可以安全地弹出栈顶\n",
    "                    stack.pop()\n",
    "                if not stack or stack[-1][0] < num2:\n",
    "                    # 如果栈顶的num2大于等于当前num2, 那就没必要将当前元组压入栈了\n",
    "                    # 因为栈顶肯定比它更优\n",
    "                    stack.append([num2, num1 + num2])\n",
    "                j += 1\n",
    "            # 此时单调栈满足num2递增, 而sm递减\n",
    "            # 二分查找首个满足条件的num2, 其对应的sm即为所求\n",
    "            k = bisect.bisect(stack, [y, -1])\n",
    "            if k < len(stack):\n",
    "                res[i] = stack[k][1]\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# 难度过高，排序+单调栈：https://leetcode.cn/problems/maximum-sum-queries/solutions/2305395/pai-xu-dan-diao-zhan-shang-er-fen-by-end-of9h/?envType=daily-question&envId=2023-11-17\n",
    "import bisect\n",
    "class Solution:\n",
    "    def maximumSumQueries(self, nums1: List[int], nums2: List[int], queries: List[List[int]]) -> List[int]:\n",
    "        ret = [-1] * len(queries)\n",
    "        # 这里需要从大到小排序，因为要求是nums1[i] >= x以及nums2[i] >= y，从大到小排序能减少查询量，即之前的一定满足大于等于这个条件\n",
    "        nums = sorted(zip(nums1, nums2), reverse=True)\n",
    "        mono = []\n",
    "        j = 0\n",
    "        # 注意这里sorted(enumerate)的写法，sorted内容为(idx, (q1, q2))这个形式！即依据q1排序的同时还带上了序号\n",
    "        for i, (q1, q2) in sorted(enumerate(queries), key=lambda x:-x[1][0]):\n",
    "            while j < len(nums) and nums[j][0] >= q1:\n",
    "                n1, n2 = nums[j]\n",
    "                s = n1 + n2\n",
    "                # 单调栈内元素格式为(n2, n1+n2)。其中n2是升序。目标是在n1+n2相等的情况下，尽可能保留n2更大的值（n1因为是单调递减，如果n1+n2相等，那么越往后的n2肯定越大，因此也更容易满足nums2[i] >= y的条件）\n",
    "                while mono and mono[-1][1] <= s:\n",
    "                    mono.pop()\n",
    "                if not mono or mono[-1][0] < n2: # 这个判断用于排除没资格入栈的n2\n",
    "                    mono.append((n2, s))\n",
    "                j += 1\n",
    "            # 在单调递增的mono中查询q2插入的位置\n",
    "            idx = bisect.bisect_left(mono, (q2, ))\n",
    "            if idx < len(mono):\n",
    "                ret[i] = mono[idx][1]\n",
    "        return ret"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maximumSumQueries(self, nums1: List[int], nums2: List[int], queries: List[List[int]]) -> List[int]:\n",
    "        ans = [-1] * len(queries)\n",
    "        a = sorted(((a, b) for a, b in zip(nums1, nums2)), key=lambda p: -p[0])\n",
    "        j = 0\n",
    "        st = []\n",
    "        for i, (x, y) in sorted(enumerate(queries), key=lambda p: -p[1][0]):\n",
    "            while j < len(a) and a[j][0] >= x:  # 下面只需关心 ay (a[j][1])\n",
    "                ax, ay = a[j]\n",
    "                while st and st[-1][1] <= ax + ay:  # ay >= st[-1][0]\n",
    "                    st.pop()\n",
    "                if not st or st[-1][0] < ay:\n",
    "                    st.append((ay, ax + ay))\n",
    "                j += 1\n",
    "            p = bisect_left(st, (y,))\n",
    "            if p < len(st):\n",
    "                ans[i] = st[p][1]\n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class BIT:\n",
    "    def __init__(self, n):\n",
    "        self.n = n\n",
    "        self.trees = [-1] * (n + 1)\n",
    "        \n",
    "    def update(self, pos, num):\n",
    "        while pos <= self.n:\n",
    "            self.trees[pos] = max(self.trees[pos], num)\n",
    "            pos += pos & (-pos)\n",
    "            \n",
    "    def query(self, pos):\n",
    "        ans = -1\n",
    "        while pos > 0:\n",
    "            ans = max(ans, self.trees[pos])\n",
    "            pos = pos & (pos - 1)\n",
    "        return ans\n",
    "\n",
    "class Solution:\n",
    "    def maximumSumQueries(self, nums1: List[int], nums2: List[int], queries: List[List[int]]) -> List[int]:\n",
    "        q_len = len(queries)\n",
    "        n = len(nums1)\n",
    "        indexed_nums1 = sorted(enumerate(nums1), key = lambda x : x[1], reverse = True)\n",
    "        sorted_nums2 = sorted(nums2)\n",
    "        num_index = 0\n",
    "        ans = [-1] * q_len\n",
    "        tree = BIT(n)\n",
    "                    \n",
    "        for q_idx, (data1, data2) in sorted(enumerate(queries), key = lambda x : x[1][0], reverse = True):\n",
    "            print(q_idx, data1, data2)\n",
    "            while num_index < n and indexed_nums1[num_index][1] >= data1:\n",
    "                data_index = indexed_nums1[num_index][0]\n",
    "                d_pos = n - bisect_left(sorted_nums2, nums2[data_index])\n",
    "                #print(\"d_pos -\", d_pos)\n",
    "                tree.update(d_pos, nums1[data_index] + nums2[data_index])\n",
    "                num_index += 1\n",
    "            q_pos = n - bisect_left(sorted_nums2, data2)\n",
    "            #print(\"query q_pos -\", q_pos)\n",
    "            ans[q_idx] = tree.query(q_pos)\n",
    "        return ans                \n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maximumSumQueries(self, nums1: List[int], nums2: List[int], queries: List[List[int]]) -> List[int]:\n",
    "        pairs = sorted(zip(nums1, nums2), key=lambda k:-k[0])\n",
    "        ans = [-1] * len(queries)\n",
    "        stack = []\n",
    "        j = 0\n",
    "        for i, (x, y) in sorted(enumerate(queries), key=lambda k:-k[1][0]):\n",
    "            while j < len(pairs) and pairs[j][0] >= x:\n",
    "                s = pairs[j][0] + pairs[j][1]\n",
    "                while stack and stack[-1][1] <= s:\n",
    "                    stack.pop()\n",
    "                if not stack or stack[-1][0] < pairs[j][1]:\n",
    "                   stack.append((pairs[j][1], s))\n",
    "                j += 1\n",
    "           \n",
    "            if stack:\n",
    "                p = bisect.bisect_left(stack, (y,))\n",
    "                if p != len(stack):\n",
    "                    ans[i] = stack[p][1]\n",
    "        return ans\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maximumSumQueries(self, nums1: List[int], nums2: List[int], queries: List[List[int]]) -> List[int]:\n",
    "        res = [-1] * len(queries)\n",
    "        a = sorted(((x, y) for x, y in zip(nums1, nums2)), key=lambda p: -p[0])\n",
    "        qs = sorted([(i, x, y) for i, (x, y) in enumerate(queries)], key=lambda x: -x[1])\n",
    "        j = 0\n",
    "        stk = [] #存(ay, ax + ay), ay递增，ax+ay递减\n",
    "        for i, x, y in qs:\n",
    "            while j < len(a) and a[j][0] >= x:\n",
    "                ax, ay = a[j]\n",
    "                while stk and stk[-1][1] <= ax + ay:\n",
    "                    stk.pop()\n",
    "                if not stk or stk[-1][0] < ay:\n",
    "                    stk.append((ay, ax + ay))\n",
    "                j += 1\n",
    "            p = bisect_left(stk, (y,))\n",
    "            if p < len(stk):\n",
    "                res[i] = stk[p][1]\n",
    "        return res\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "import bisect\n",
    "\n",
    "class Solution:\n",
    "    def maximumSumQueries(self, nums1: List[int], nums2: List[int], queries: List[List[int]]) -> List[int]:\n",
    "        m = len(nums1)\n",
    "\n",
    "        nums = [(nums1[i], nums2[i], nums1[i] + nums2[i]) for i in range(m)]\n",
    "        nums.sort(key=lambda x: -x[0])\n",
    "\n",
    "        qi = [(queries[i][0], queries[i][1], i) for i in range(len(queries))]\n",
    "        qi.sort(key=lambda x: -x[0])\n",
    "\n",
    "        ret = [-1] * len(queries)\n",
    "        stack = []\n",
    "        j = 0\n",
    "        for x, y, i in qi:\n",
    "            while j < m and nums[j][0] >= x:\n",
    "                xj, yj, xyj = nums[j]\n",
    "                while stack and xyj >= stack[-1][1]:\n",
    "                    stack.pop()\n",
    "                if not stack or yj > stack[-1][0]:\n",
    "                    stack.append((yj, xyj))\n",
    "                j += 1\n",
    "            k = bisect.bisect_left(stack, (y, 0))\n",
    "            if k == len(stack):\n",
    "                continue\n",
    "            ret[i] = stack[k][1]\n",
    "        return ret\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maximumSumQueries(self, nums1: List[int], nums2: List[int], queries: List[List[int]]) -> List[int]:\n",
    "        pairs = sorted([(a, b) for a, b in zip(nums1, nums2)], reverse=True)\n",
    "        j = 0\n",
    "        res = [-1 for _ in range(len(queries))]\n",
    "        stack = []\n",
    "        for i, (x, y) in sorted(enumerate(queries), key=lambda x: -x[1][0]):\n",
    "            while j < len(pairs) and pairs[j][0] >= x:\n",
    "                n1, n2 = pairs[j]\n",
    "                while stack and stack[-1][1] <= n1 + n2:\n",
    "                    stack.pop()\n",
    "                if not stack or stack[-1][0] < n2:\n",
    "                    stack.append((n2, (n1 + n2)))\n",
    "                j += 1\n",
    "            l, r = -1, len(stack)\n",
    "            while l + 1 < r:\n",
    "                mid = l + (r - l) // 2\n",
    "                if stack[mid][0] < y:\n",
    "                    l = mid\n",
    "                else:\n",
    "                    r = mid\n",
    "            if r < len(stack):\n",
    "                res[i] = stack[r][1]\n",
    "        return res\n",
    "                \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from sortedcontainers import SortedKeyList\n",
    "\n",
    "class Solution:\n",
    "    def maximumSumQueries(self, nums1: List[int], nums2: List[int], queries: List[List[int]]) -> List[int]:\n",
    "        a = sorted(list(zip(nums1, nums2)), key=lambda x:-x[0])\n",
    "        j = 0\n",
    "        st = [] # store (y, x + y), with ascending y and descending x+y\n",
    "        ans = [-1] * len(queries)\n",
    "        for i, (x, y) in sorted(enumerate(queries), key=lambda x:-x[1][0]):\n",
    "            while j < len(a) and a[j][0] >= x:\n",
    "                ax, ay = a[j]\n",
    "                while st and st[-1][1] <= ax + ay: # 去掉无用的，这里蕴含了 ay >= st[-1][0] 因为 x 是descending的\n",
    "                    st.pop()\n",
    "                if not st or st[-1][0] < ay:\n",
    "                    st.append((ay, ax+ay))\n",
    "                j += 1\n",
    "            p = bisect_left(st, (y,))\n",
    "            if p < len(st):\n",
    "                ans[i] = st[p][1]\n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maximumSumQueries(self, nums1: List[int], nums2: List[int], queries: List[List[int]]) -> List[int]:\n",
    "        arr = sorted([(i, e[0], e[1]) for i, e in enumerate(queries)], key=lambda x: -x[1])\n",
    "        stack = []\n",
    "        n = len(nums1)\n",
    "        nums = sorted(zip(nums2, nums1), key=lambda x: (-x[1], x[0]))\n",
    "        now = 0\n",
    "        res = [-1]*len(arr)\n",
    "        for idx, x, y in arr:\n",
    "            while now < n and nums[now][1] >= x:\n",
    "                n2, n1 = nums[now]\n",
    "                while stack and stack[-1][1] <= n1+n2:\n",
    "                    stack.pop()\n",
    "                if not stack or stack[-1][0] < n2:\n",
    "                    stack.append((n2, n1+n2))\n",
    "                now += 1\n",
    "            where = bisect_left([a for a, b in stack], y)\n",
    "            if where < len(stack):\n",
    "                res[idx] = stack[where][-1]\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from functools import cache\r\n",
    "\r\n",
    "\r\n",
    "class Solution:\r\n",
    "    def maximumSumQueries(self, nums1: List[int], nums2: List[int], queries: List[List[int]]) -> List[int]:\r\n",
    "        sums = sorted(((a+b, a, b)\r\n",
    "                      for a, b in zip(nums1, nums2)), reverse=True)\r\n",
    "\r\n",
    "        @cache\r\n",
    "        def query(q1, q2):\r\n",
    "            for s, n1, n2 in sums:\r\n",
    "                if s < q1+q2:\r\n",
    "                    return (-1)\r\n",
    "                if n1 >= q1 and n2 >= q2:\r\n",
    "                    return (s)\r\n",
    "            return (-1)\r\n",
    "        return ([query(q1, q2) for q1, q2 in queries])"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maximumSumQueries(self, nums1: List[int], nums2: List[int], queries: List[List[int]]) -> List[int]:\n",
    "        # 暴力+缓存\n",
    "        sums = list()\n",
    "        for i in range(len(nums1)):\n",
    "            a = nums1[i]\n",
    "            b = nums2[i]\n",
    "            sums.append((a + b, a, b))\n",
    "        sums.sort(reverse=True)\n",
    "\n",
    "        @cache\n",
    "        def query(q1, q2):\n",
    "            for s, n1, n2 in sums:\n",
    "                if s < q1 + q2:\n",
    "                    return -1\n",
    "                if n1 >= q1 and n2 >= q2:\n",
    "                    return s\n",
    "            return -1\n",
    "        \n",
    "        ans = []\n",
    "        for q1, q2 in queries:\n",
    "            a = query(q1, q2)\n",
    "            ans.append(a)\n",
    "        return ans\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maximumSumQueries(self, nums1: List[int], nums2: List[int], queries: List[List[int]]) -> List[int]:\n",
    "        nums = [(nums1[i], nums2[i]) for i in range(len(nums1))]\n",
    "        nums.sort(key=lambda x: (x[0], x[1]), reverse=True)\n",
    "        q = [(x[0], x[1], i) for i, x in enumerate(queries)]\n",
    "        q.sort(key=lambda x: (x[0], x[1]), reverse=True)\n",
    "\n",
    "        res = [-1] * len(queries)\n",
    "        stk = []\n",
    "        i = 0\n",
    "        for x in q:\n",
    "            r = -1\n",
    "            while i < len(nums):\n",
    "                if nums[i][0] >= x[0]:\n",
    "                    while stk:\n",
    "                        if stk[-1][1] < nums[i][0] + nums[i][1]:\n",
    "                            stk.pop()\n",
    "                        else:\n",
    "                            break\n",
    "                    if not stk or stk[-1][0] < nums[i][1]:\n",
    "                        stk.append((nums[i][1], nums[i][0] + nums[i][1]))\n",
    "                else:\n",
    "                    break\n",
    "                i += 1\n",
    "            if stk:\n",
    "                left = 0\n",
    "                right = len(stk) - 1\n",
    "                while left < right:\n",
    "                    mid = (left + right) // 2\n",
    "                    if stk[mid][0] < x[1]:\n",
    "                        left = mid + 1\n",
    "                    else:\n",
    "                        right = mid\n",
    "                if stk[left][0] >= x[1]:\n",
    "                    r = stk[left][1]\n",
    "            res[x[2]] = r\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "import bisect\n",
    "\n",
    "class Solution:\n",
    "    def maximumSumQueries(self, nums1: List[int], nums2: List[int], queries: List[List[int]]) -> List[int]:\n",
    "        table = [(nums1[i]+nums2[i], nums1[i], nums2[i]) for i in range(len(nums1))]\n",
    "        tableBySum = sorted(table, key=lambda t:-t[0])\n",
    "\n",
    "        @functools.cache\n",
    "        def query(x:int, y:int) -> int:\n",
    "            for item in tableBySum:\n",
    "                if item[1] >= x and item[2] >= y:\n",
    "                    return item[0]\n",
    "            return -1\n",
    "\n",
    "        return [query(q[0], q[1]) for q in queries]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maximumSumQueries(self, nums1: List[int], nums2: List[int], queries: List[List[int]]) -> List[int]:\n",
    "        nums = [(a, b) for a, b in zip(nums1, nums2)]\n",
    "        nums.sort(reverse=True)\n",
    "\n",
    "        n = len(nums)\n",
    "        m = len(queries)\n",
    "\n",
    "        for i in range(m):\n",
    "            queries[i].append(i)\n",
    "\n",
    "        queries.sort(reverse=True)\n",
    "\n",
    "        ret = [-1] * m\n",
    "\n",
    "        i = 0\n",
    "        st = []\n",
    "\n",
    "        for x, y, qi in queries:\n",
    "            while i < n and nums[i][0] >= x:\n",
    "                a, b = nums[i]\n",
    "                while st and st[-1][1] <= a + b:\n",
    "                    st.pop()\n",
    "\n",
    "                if not st or st[-1][0] < b:\n",
    "                    st.append((b, a + b))\n",
    "\n",
    "                i += 1\n",
    "\n",
    "            t = bisect_left(st, (y, 0))\n",
    "\n",
    "            if t < len(st):\n",
    "                ret[qi] = st[t][1]\n",
    "\n",
    "        return ret"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maximumSumQueries(self, nums1: List[int], nums2: List[int], queries: List[List[int]]) -> List[int]:\n",
    "        a = sorted((a, b) for a, b in zip(nums1, nums2))\n",
    "        for i, arr in enumerate(queries):\n",
    "            arr.append(i)\n",
    "        queries.sort(key=lambda i: -i[0])\n",
    "\n",
    "        st = []\n",
    "        ans = [-1] * len(queries)\n",
    "        i = len(a) - 1\n",
    "        for x, y, idx in queries:\n",
    "            while i >= 0 and a[i][0] >= x:\n",
    "                ax, ay = a[i]\n",
    "                while st and st[-1][1] <= ax + ay:\n",
    "                    st.pop()\n",
    "                if not st or st[-1][0] < ay:\n",
    "                    st.append((ay, ax + ay))\n",
    "                i -= 1\n",
    "            j = bisect_left(st, (y, ))\n",
    "            if j < len(st) and st[j][1] >= x:\n",
    "                ans[idx] = st[j][1]\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class linetree:\n",
    "    def __init__(self,l,r,val=0):\n",
    "        self.tree = {1:val}    #如果l=0，可以=[val]*(4*(r-l+1))\n",
    "        self.lazy = {1:1}         #如果很稀疏，则用字典\n",
    "        self.lm=l\n",
    "        self.rm=r\n",
    "        self.default=val\n",
    "\n",
    "    def update(self, start: int, end: int, val):\n",
    "        self._update(start,end,self.lm,self.rm,1,val)\n",
    "        \n",
    "    def _update(self, start: int, end: int, l: int, r: int, idx: int, val):\n",
    "        # print(idx,list(self.tree.keys()),l,r,start,end)\n",
    "        if r < start or end < l:\n",
    "            if idx not in self.tree:\n",
    "                # print(idx,list(self.tree.keys()))\n",
    "                self.tree[idx]=self.default\n",
    "                self.lazy[idx]=1\n",
    "            return\n",
    "        if start <= l and r <= end:\n",
    "            self.tree[idx] =val\n",
    "            self.lazy[idx] = 1\n",
    "        else:\n",
    "            mid = (l + r) // 2\n",
    "            self._update(start, end, l, mid, idx * 2,val)\n",
    "            self._update(start, end, mid + 1, r, idx * 2 + 1,val)\n",
    "            self.tree[idx] = max(self.tree[idx * 2], self.tree[idx * 2 + 1])\n",
    "            self.lazy[idx]=0\n",
    "            \n",
    "    def query(self,start,end):\n",
    "        return self._query(start,end,self.lm,self.rm,1)\n",
    "        \n",
    "    def _query(self,start,end,l,r,idx):\n",
    "        # if idx not in self.lazy and idx in self.tree:\n",
    "        #     print(idx,list(self.lazy.keys()),list(self.tree.keys()))\n",
    "        if r<start or end<l :\n",
    "            return self.default\n",
    "        if (start <=l and r<=end) or self.lazy[idx]==1:\n",
    "            return self.tree[idx]\n",
    "        mid=(l+r)//2\n",
    "        return max(self._query(start,end,l,mid,idx*2),self._query(start,end,mid+1,r,idx*2+1))\n",
    "    \n",
    "class Solution:\n",
    "    def maximumSumQueries(self, nums1: List[int], nums2: List[int], queries: List[List[int]]) -> List[int]:\n",
    "        n=len(nums1)\n",
    "        nl=[[] for _ in range(n)]\n",
    "        for i in range(n):\n",
    "            nl[i]=[nums1[i],nums2[i],i]\n",
    "        nl.sort(key=lambda x:(-x[0],-x[1]))\n",
    "        nq=len(queries)\n",
    "        for i in range(nq):\n",
    "            queries[i].append(i)\n",
    "        queries.sort(reverse=1)\n",
    "        res=[-1]*nq\n",
    "        maxv=max(nums2)\n",
    "        tr=linetree(0,maxv,-1)\n",
    "        # s=set()\n",
    "        maxv=0\n",
    "        p=0\n",
    "        for x,y,i in queries:\n",
    "            while p<n and nl[p][0]>=x:\n",
    "                if nl[p][1] >maxv:\n",
    "                    # s.add(nl[p][1])\n",
    "                    maxv=nl[p][1]\n",
    "                    tr.update(nl[p][1],nl[p][1],nl[p][0]+nl[p][1])\n",
    "                p+=1\n",
    "            res[i]=tr.query(y,maxv)\n",
    "        return res\n",
    "\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maximumSumQueries(self, nums1: List[int], nums2: List[int], queries: List[List[int]]) -> List[int]:\n",
    "        lenth = len(nums1)\n",
    "        nums = list(zip(nums1,nums2))\n",
    "        # 二维递减排序\n",
    "        nums.sort(key = lambda x:(-x[0],-x[1])) \n",
    "        #单调栈中保存的是按照nums1逆序排列时 \n",
    "        #nums2中的正序排序的子序列\n",
    "        # 利用单调栈，保存j递增的列表的下标\n",
    "        stackj = [0]\n",
    "        for i in range(1,lenth):\n",
    "            if nums[i][1] > nums[stackj[-1]][1]:\n",
    "                stackj.append(i)\n",
    "        result = []\n",
    "        @cache # 缓存可以加速重复的查询值\n",
    "        def find(x,y):\n",
    "            start = 0\n",
    "            maxij = -1            \n",
    "            while start<len(stackj):   \n",
    "                # 从单调栈调取查询的下标\n",
    "                index = stackj[start] \n",
    "                # 如果当前的nums1对应值不符合条件 后面的不用找了\n",
    "                if nums[index][0] < x: \n",
    "                    break      \n",
    "                if nums[index][1] >= y: \n",
    "                    maxij = max(maxij,sum(nums[index]))\n",
    "                start += 1 # 查询单调栈中下一个坐标\n",
    "            return maxij\n",
    "\n",
    "        for x,y in queries:\n",
    "            result.append(find(x,y))\n",
    "\n",
    "        return result"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maximumSumQueries(self, nums1: List[int], nums2: List[int], queries: List[List[int]]) -> List[int]:\n",
    "        x=zip(nums1,nums2)\n",
    "        sortednums=sorted(x,key=lambda x:-x[0]) # 降序排列\n",
    "        print(sortednums)\n",
    "        sortedqueries=sorted([[i,x,y] for i,(x,y) in enumerate(queries)],key=lambda x:-x[1])\n",
    "        print(sortedqueries)\n",
    "        n=len(sortednums)\n",
    "        ans=[-1]*len(queries)\n",
    "        stack=[]\n",
    "\n",
    "        j=0\n",
    "        for i,x,y in sortedqueries:\n",
    "            while j<n and sortednums[j][0]>=x:\n",
    "                num1,num2=sortednums[j]\n",
    "                while stack and stack[-1][1]<=num1+num2: # 说明此时的num1+num2比之前的大，并且num2也比之前的大\n",
    "                    stack.pop() # 在这种情况下之前的数对已经没有用了，因为现在的num2覆盖的范围已经包含了比他小的num2覆盖的范围\n",
    "                if not stack or stack[-1][0]<num2:\n",
    "                    # 因为在之前的操作中已经保证stack[-1][1]>num1+num2,这时如果num2<stack[-1][0],那这个num2已经没有任何作用了\n",
    "                    # 只有在num2比之前的数打的时候才可能在后续查找中发挥作用\n",
    "                    stack.append([num2,num1+num2])\n",
    "                j+=1\n",
    "            m=len(stack)\n",
    "            pos=bisect_left(stack,[y,0])\n",
    "            if pos<m:\n",
    "                ans[i]=stack[pos][1]\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maximumSumQueries(self, nums1: List[int], nums2: List[int], queries: List[List[int]]) -> List[int]:\n",
    "        tmp=(sorted([(nums1[i], nums2[i]) for i in range(len(nums1))], key=lambda x: sum(x), reverse=True))\n",
    "        ans=[]\n",
    "        d={}\n",
    "        for x,y in queries:\n",
    "            s=str(x)+str(y)\n",
    "            if s not in d:\n",
    "                res=-1\n",
    "                for j in tmp:\n",
    "                    if j[0]>=x and j[1]>=y:\n",
    "                        res=sum(j)\n",
    "                        break\n",
    "                d[s]=res\n",
    "                ans.append(res)\n",
    "            else:\n",
    "                ans.append(d[s])\n",
    "        return ans\n",
    "                "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maximumSumQueries(self, nums1: List[int], nums2: List[int], queries: List[List[int]]) -> List[int]:\n",
    "        sortedNums = sorted([[a, b] for a, b in zip(nums1, nums2)], key = lambda x: -x[0])\n",
    "        sortedQueries = sorted([[i, x, y] for i, (x, y) in enumerate(queries)], key=lambda q:-q[1])\n",
    "        stack = []\n",
    "        answer = [-1] * len(queries)\n",
    "        j = 0\n",
    "        for i, x, y in sortedQueries:\n",
    "            while j < len(sortedNums) and sortedNums[j][0] >= x:\n",
    "                num1, num2 = sortedNums[j]\n",
    "                while stack and stack[-1][1] <= num1 + num2:\n",
    "                    stack.pop()\n",
    "                if not stack or stack[-1][0] < num2:\n",
    "                    stack.append([num2, num1 + num2])\n",
    "                j += 1\n",
    "            k = bisect_left(stack, [y, 0])\n",
    "            if k < len(stack):\n",
    "                answer[i] = stack[k][1]\n",
    "        return answer"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maximumSumQueries(self, nums1: List[int], nums2: List[int], queries: List[List[int]]) -> List[int]:\n",
    "        sortedNums = sorted([[a, b] for a, b in zip(nums1, nums2)], key = lambda x: -x[0])\n",
    "        sortedQueries = sorted([[i, x, y] for i, (x, y) in enumerate(queries)], key=lambda q:-q[1])\n",
    "        stack = []\n",
    "        answer = [-1] * len(queries)\n",
    "        j = 0\n",
    "        for i, x, y in sortedQueries:\n",
    "            while j < len(sortedNums) and sortedNums[j][0] >= x:\n",
    "                num1, num2 = sortedNums[j]\n",
    "                while stack and stack[-1][1] <= num1 + num2:\n",
    "                    stack.pop()\n",
    "                if not stack or stack[-1][0] < num2:\n",
    "                    stack.append([num2, num1 + num2])\n",
    "                j += 1\n",
    "            k = bisect_left(stack, [y, 0])\n",
    "            if k < len(stack):\n",
    "                answer[i] = stack[k][1]\n",
    "        return answer\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maximumSumQueries(self, nums1: List[int], nums2: List[int], queries: List[List[int]]) -> List[int]:\n",
    "        import bisect\n",
    "        n = len(nums1)\n",
    "        m = len(queries)\n",
    "        res = [-1] * m\n",
    "        eq = []\n",
    "        for i in range(m):\n",
    "            eq.append([i, queries[i][0], queries[i][1]])\n",
    "        eq.sort(key = lambda x: -x[1])\n",
    "        nums = []\n",
    "        for i in range(n):\n",
    "            nums.append([nums1[i], nums2[i], nums1[i] + nums2[i]])\n",
    "        nums.sort(reverse = True)\n",
    "\n",
    "        vals = list(set(nums2))\n",
    "        vals.sort()\n",
    "        l = len(vals)\n",
    "        dic = {}\n",
    "        for i in range(l):\n",
    "            dic[vals[i]] = i\n",
    "        self.blockSize = int(math.sqrt(l))\n",
    "        self.blockNum = int(math.ceil(l / self.blockSize))\n",
    "        self.blockMax = [-1] * self.blockNum\n",
    "        self.ovals = [-1] * l\n",
    "\n",
    "        j = 0\n",
    "        for i in range(m):\n",
    "            k, xmin, ymin = eq[i]\n",
    "            while j < n and nums[j][0] >= xmin:\n",
    "                x, y, z = nums[j]\n",
    "                self.updateMax(dic[y], z)\n",
    "                j += 1\n",
    "            t = bisect.bisect_left(vals, ymin)\n",
    "            if t < l:\n",
    "                v = self.getMax(t)\n",
    "                res[k] = v\n",
    "        return res\n",
    "\n",
    "    def getMax(self, ge):\n",
    "        res = -1\n",
    "        i = ge // self.blockSize\n",
    "        for j in range(i + 1, self.blockNum):\n",
    "            res = max(res, self.blockMax[j])\n",
    "        for j in range(ge, min((i + 1) * self.blockSize, len(self.ovals))):\n",
    "            res = max(res, self.ovals[j])\n",
    "        return res\n",
    "\n",
    "    def updateMax(self, i, v):\n",
    "        self.ovals[i] = max(self.ovals[i], v)\n",
    "        j = i // self.blockSize\n",
    "        self.blockMax[j] = max(self.blockMax[j], self.ovals[i])\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maximumSumQueries(self, nums1: List[int], nums2: List[int], queries: List[List[int]]) -> List[int]:\n",
    "        sz = 0\n",
    "        tr = []\n",
    "\n",
    "        def lowbit(x):\n",
    "            return x & -x\n",
    "        def add(a, b):\n",
    "            i = a\n",
    "            while i <= sz:\n",
    "                tr[i] = max(tr[i], b)\n",
    "                i += lowbit(i)\n",
    "        def query(x):\n",
    "            ans, i = -1, x\n",
    "            while i > 0:\n",
    "                ans = max(ans, tr[i])\n",
    "                i -= lowbit(i)\n",
    "            return ans\n",
    "        \n",
    "        n, m = len(nums1), len(queries)\n",
    "        # 构建新的 nums 和 nq\n",
    "        nums = [(nums1[i], nums2[i]) for i in range(n)]\n",
    "        nq = [(queries[i][0], queries[i][1], i) for i in range(m)]\n",
    "        \n",
    "        #  对要添加到树状数组的 nums[i][1] 和 nq[i][1] 进行离散化（构建映射字典, 将原值映射到 [0, m - 1])\n",
    "        unique_set = set()\n",
    "        for x in nums:\n",
    "            unique_set.add(x[1])\n",
    "        for q in nq:\n",
    "            unique_set.add(q[1])\n",
    "        unique_list = list(unique_set)\n",
    "        unique_list.sort()\n",
    "        sz = len(unique_list)\n",
    "        mapping = {val: idx for idx, val in enumerate(unique_list)}\n",
    "        \n",
    "        # 调整询问顺序, 解决其中一维限制\n",
    "        nums.sort(key=lambda x: x[0], reverse=True)\n",
    "        nq.sort(key=lambda x: x[0], reverse=True)\n",
    "        \n",
    "        tr = [-1] * (sz + 10)\n",
    "        \n",
    "        ans = [0] * m\n",
    "        idx = 0\n",
    "        for x, y, i in nq:\n",
    "            # 扫描所有满足 nums[idx][0] >= x 的数对, 添加到树状数组中（其中离散值作为位置信息, 数对和作为值信息）\n",
    "            while idx < n and nums[idx][0] >= x:\n",
    "                add(sz - mapping[nums[idx][1]], nums[idx][0] + nums[idx][1])\n",
    "                idx += 1\n",
    "            ans[i] = query(sz - mapping[y])  # 查询树状数组中的最值\n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maximumSumQueries(self, nums1: List[int], nums2: List[int], queries: List[List[int]]) -> List[int]:\n",
    "        nums = [[nums1[j]+nums2[j],nums1[j],nums2[j]] for j in range(len(nums1))]\n",
    "        nums.sort(key=lambda x:-x[0])\n",
    "        answer = []\n",
    "        mp = {}\n",
    "        for query in queries:\n",
    "            key = str(query)\n",
    "            if key in mp:\n",
    "                answer.append(mp[key])  # 降序排列，所以就加入的是最大值\n",
    "            else:\n",
    "                val = -1\n",
    "                for num in nums:\n",
    "                    if num[1] >= query[0] and num[2] >= query[1]:\n",
    "                        val = num[0]\n",
    "                        break\n",
    "                mp[key] = val\n",
    "                answer.append(val)\n",
    "        return answer\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maximumSumQueries(self, nums1: List[int], nums2: List[int], queries: List[List[int]]) -> List[int]:\n",
    "        \n",
    "        ret = []\n",
    "        tmp = (sorted([(nums1[i], nums2[i]) for i in range(len(nums1))], key=lambda x: sum(x), reverse=True))\n",
    "        qmap = {}\n",
    "        for i in queries:\n",
    "            if str(i) not in qmap:\n",
    "                curr_max = -1\n",
    "                for j in tmp:\n",
    "                    if j[0] >= i[0] and j[1] >= i[1]:\n",
    "                        curr_max = sum(j)\n",
    "                        break\n",
    "                qmap[str(i)] = curr_max\n",
    "                ret.append(curr_max)\n",
    "            else:\n",
    "                ret.append(qmap[str(i)])\n",
    "        return ret\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def part(self,stack,l,r,y):\n",
    "        while(l<r):\n",
    "            mid =(l+r)//2\n",
    "            if stack[mid][1]<y:\n",
    "                l=mid+1\n",
    "            else:\n",
    "                r=mid\n",
    "        if l>=len(stack) or stack[l][1]<y:\n",
    "            return -1\n",
    "        return l\n",
    "\n",
    "    def maximumSumQueries(self, nums1: List[int], nums2: List[int], queries: List[List[int]]) -> List[int]:\n",
    "        nums = list(zip(nums1, nums2))\n",
    "        nums.sort(reverse=True)\n",
    "        ones=[]\n",
    "        for i in range(len(queries)):\n",
    "            ones.append(i)\n",
    "        queries=list(zip(queries,ones))\n",
    "        queries.sort(reverse=True)\n",
    "        stack = []\n",
    "        num = 0\n",
    "        i = 0\n",
    "        res=[]\n",
    "        for query in queries:\n",
    "            i += 1\n",
    "            while num < len(nums) and nums[num][0] >= query[0][0]:\n",
    "                if stack and nums[num][1] <= stack[-1][1]:\n",
    "                    num += 1\n",
    "                    continue\n",
    "                while stack and nums[num][1] + nums[num][0] >= stack[-1][0] + stack[-1][1]:\n",
    "                    stack.pop()\n",
    "                stack.append(nums[num])\n",
    "                num += 1\n",
    "            print(stack)\n",
    "            l=self.part(stack,0,len(stack)-1,query[0][1])\n",
    "            if l==-1:\n",
    "                res.append((query[1],-1))\n",
    "            else:\n",
    "                res.append((query[1],stack[l][0]+stack[l][1]))\n",
    "        res.sort()\n",
    "        ans=[]\n",
    "        for i in res:\n",
    "            ans.append(i[1])\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Bit:\n",
    "    def __init__(self,n):\n",
    "        self.tree = [-1] * (n+1)\n",
    "        self.n = n\n",
    "    \n",
    "    @staticmethod\n",
    "    def lowbit(x):\n",
    "        return x & -x\n",
    "    \n",
    "    def add(self, i, v):\n",
    "        while i > 0:\n",
    "            self.tree[i] = max(self.tree[i], v)\n",
    "            i -= self.lowbit(i)\n",
    "\n",
    "    def query(self, i):\n",
    "        ans = -1\n",
    "        while i <= self.n:\n",
    "            ans = max(ans, self.tree[i])\n",
    "            i += self.lowbit(i)\n",
    "        return ans\n",
    "\n",
    "class Solution:\n",
    "    def maximumSumQueries(self, nums1: List[int], nums2: List[int], queries: List[List[int]]) -> List[int]:\n",
    "        ans = [-1] * len(queries)\n",
    "        a = sorted([(x,y) for x,y in zip(nums1,nums2)], key=lambda x:-x[0])\n",
    "        j = 0 # a的下标\n",
    "\n",
    "        mp = {}\n",
    "        for i, x in enumerate(sorted(set(nums2+[y for _,y in queries])), start=1):\n",
    "            # 可能有重复值，所以i != len(mp) + 1\n",
    "            mp[x] = i\n",
    "        bit = Bit(i)\n",
    "\n",
    "        for i, (x,y) in sorted(enumerate(queries), key=lambda x:-x[1][0]):\n",
    "            while j < len(a) and a[j][0] >= x:\n",
    "                ax, ay = a[j]\n",
    "                bit.add(mp[ay], ax+ay)\n",
    "                j += 1\n",
    "            ans[i] = bit.query(mp[y])\n",
    "\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "def stackappend(arr,e):\n",
    "    while len(arr)!=0:\n",
    "        if arr[-1][1]<=e[1]:\n",
    "            arr.pop()\n",
    "        else:\n",
    "            break\n",
    "    arr.append(e)\n",
    "\n",
    "def merge(arr1,arr2):\n",
    "    ret = []\n",
    "    c1 = 0\n",
    "    c2 = 0\n",
    "    while c1<len(arr1) and c2<len(arr2):\n",
    "        if arr1[c1]<=arr2[c2]:\n",
    "            stackappend(ret,arr1[c1])\n",
    "            c1 += 1\n",
    "        else:\n",
    "            stackappend(ret,arr2[c2])\n",
    "            c2 += 1\n",
    "    while c1<len(arr1):\n",
    "        stackappend(ret,arr1[c1])\n",
    "        c1 += 1\n",
    "    \n",
    "    while c2<len(arr2):\n",
    "        stackappend(ret,arr2[c2])\n",
    "        c2 += 1\n",
    "    \n",
    "    return ret\n",
    "\n",
    "def bisect(arr,tgt):\n",
    "    begin = 0\n",
    "    end = len(arr)-1\n",
    "    while begin<=end:\n",
    "        mid = (begin+end)//2\n",
    "        if mid==begin:\n",
    "            if arr[begin][0]>=tgt:\n",
    "                return begin\n",
    "            if arr[end][0]>=tgt:\n",
    "                return end\n",
    "            return None\n",
    "        if arr[mid][0]<tgt:\n",
    "            begin = mid\n",
    "        else:\n",
    "            end = mid\n",
    "    else:\n",
    "        return None\n",
    "\n",
    "class Solution:\n",
    "    def maximumSumQueries(self, nums1: List[int], nums2: List[int], queries: List[List[int]]) -> List[int]:\n",
    "        qarr = []\n",
    "        ret = [None]*len(queries)\n",
    "        for i in range(len(queries)):\n",
    "            q = queries[i]\n",
    "            qarr.append([q[0],q[1],i])\n",
    "        qarr.sort(reverse=True)\n",
    "\n",
    "        nums = []\n",
    "        for i in range(len(nums1)):\n",
    "            nums.append([nums1[i],nums2[i]])\n",
    "        nums.sort(reverse=True)\n",
    "\n",
    "        #print(qarr)\n",
    "        #print(nums)\n",
    "\n",
    "        cur = 0\n",
    "        yarr = [] # y,v\n",
    "\n",
    "        for q in qarr:\n",
    "            tarr = []\n",
    "            while cur<len(nums) and nums[cur][0]>=q[0]:\n",
    "                tarr.append([nums[cur][1],nums[cur][0] + nums[cur][1]])\n",
    "                cur += 1\n",
    "            tarr.sort()\n",
    "\n",
    "            #print(\"y,tarr\",yarr,tarr)\n",
    "\n",
    "            nyarr = merge(yarr,tarr) #单调合并\n",
    "            yarr = nyarr\n",
    "\n",
    "            #print(\"yarr\",yarr,q[1])\n",
    "\n",
    "            #在yarr中bisect大于等于q[1]的最左元素,取v值\n",
    "            idx = bisect(yarr,q[1])\n",
    "\n",
    "            if idx==None:\n",
    "                ret[q[2]] = -1\n",
    "            else:\n",
    "                ret[q[2]] = yarr[idx][1]\n",
    "\n",
    "        return ret\n",
    "\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maximumSumQueries(self, nums1: List[int], nums2: List[int], queries: List[List[int]]) -> List[int]:\n",
    "        nums = list(zip(nums1, nums2))\n",
    "        nums.sort(reverse=True)\n",
    "        queries = [queries[i] + [i] for i in range(len(queries))]\n",
    "        queries.sort(reverse=True)\n",
    "        N = 10 ** 9 + 1\n",
    "        st = SegmentTree()\n",
    "        j = 0\n",
    "        ans = [-1] * len(queries)\n",
    "        for i in range(len(queries)):\n",
    "            while j < len(nums) and nums[j][0] >= queries[i][0]:\n",
    "                st.update(st.root, 0, N, nums[j][1], nums[j][0] + nums[j][1])\n",
    "                j += 1\n",
    "            ans[queries[i][2]] = st.query(st.root, 0, N, queries[i][1], N)\n",
    "        return ans\n",
    "\n",
    "\n",
    "class Node:\n",
    "    __slots__ = ['val', 'left', 'right']\n",
    "\n",
    "    def __init__(self, left=None, right=None, val=-1) -> None:\n",
    "        self.left, self.right, self.val = left, right, val\n",
    "\n",
    "\n",
    "class SegmentTree:\n",
    "    def __init__(self):\n",
    "        self.root = Node()\n",
    "\n",
    "    def update(self, node, s, e, index, val):\n",
    "        # 动态开点\n",
    "        if not node:\n",
    "            node = Node()\n",
    "        if s == e:\n",
    "            node.val = max(node.val,val)\n",
    "            return node\n",
    "        mid = (s + e) >> 1\n",
    "        if index <= mid:\n",
    "            node.left = self.update(node.left, s, mid, index, val)\n",
    "        if index > mid:\n",
    "            node.right = self.update(node.right, mid + 1, e, index, val)\n",
    "        node.val = max(node.left.val if node.left else 0, node.right.val if node.right else 0)\n",
    "        return node\n",
    "\n",
    "    def query(self, node, s, e, l, r):\n",
    "        if not node:\n",
    "            return -1\n",
    "        if l <= s and e <= r:\n",
    "            return node.val\n",
    "        mid = (s + e) >> 1\n",
    "        ans = -1\n",
    "        if l <= mid:\n",
    "            ans = max(ans, self.query(node.left, s, mid, l, r))\n",
    "        if r > mid:\n",
    "            ans = max(ans, self.query(node.right, mid + 1, e, l, r))\n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maximumSumQueries(\n",
    "        self, nums1: List[int], nums2: List[int], queries: List[List[int]]\n",
    "    ) -> List[int]:\n",
    "        ans = [-1] * len(queries)\n",
    "        st = []\n",
    "        arr = sorted(zip(nums1, nums2))  # 默认按照第一个维度排序\n",
    "        for i in range(len(queries)):\n",
    "            queries[i].append(i)\n",
    "        queries.sort(key=lambda x: -x[0])  # 按 x 从大到小排序\n",
    "        idx = len(nums1) - 1\n",
    "        for x, y, qid in queries:\n",
    "            # 是不是可以加入这个区间\n",
    "            while idx > -1 and arr[idx][0] >= x:\n",
    "                ax, ay = arr[idx]\n",
    "                # 要么是一个空的栈 要么就是 哪些数据是无用的\n",
    "                while st and st[-1][1] <= ax + ay:\n",
    "                    st.pop()\n",
    "                if not st or ay > st[-1][0]:\n",
    "                    st.append((ay, ax + ay))\n",
    "                idx -= 1\n",
    "            # ax + ay从低到顶增加 ay从低到顶减少\n",
    "            i = bisect_left(st, (y,))\n",
    "            if i != len(st):\n",
    "                ans[qid] = st[i][1]\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maximumSumQueries(self, nums1: List[int], nums2: List[int], queries: List[List[int]]) -> List[int]:\n",
    "        sums = {}\n",
    "        for i in range(len(nums1)):\n",
    "            sum = nums1[i] + nums2[i]\n",
    "            if sum not in sums:\n",
    "                sums[sum] = [(nums1[i], nums2[i])]\n",
    "            else:\n",
    "                sums[sum].append((nums1[i], nums2[i]))\n",
    "        sorted_keys = sorted(sums.keys(), reverse=True)\n",
    "        result = []\n",
    "        cache = {}\n",
    "        for q in queries:\n",
    "            if (q[0], q[1]) in cache:\n",
    "                result.append(cache[(q[0], q[1])])\n",
    "                continue\n",
    "            should_break = False\n",
    "            for k in sorted_keys:\n",
    "                if should_break:\n",
    "                    break\n",
    "                for p in sums[k]:\n",
    "                    if p[0] >= q[0] and p[1] >= q[1]:\n",
    "                        cache[(q[0], q[1])] = k\n",
    "                        result.append(k)\n",
    "                        should_break = True\n",
    "                        break\n",
    "            if not should_break:\n",
    "                result.append(-1)\n",
    "        return result\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "import typing\n",
    "\n",
    "\n",
    "class SegTree:\n",
    "    def __init__(self,\n",
    "                 op: typing.Callable[[typing.Any, typing.Any], typing.Any],\n",
    "                 e: typing.Any,\n",
    "                 v: typing.Union[int, typing.List[typing.Any]]) -> None:\n",
    "        self._op = op\n",
    "        self._e = e\n",
    "\n",
    "        if isinstance(v, int):\n",
    "            v = [e] * v\n",
    "\n",
    "        self._n = len(v)\n",
    "        self._log = (self._n - 1).bit_length()\n",
    "        self._size = 1 << self._log\n",
    "        self._d = [e] * (2 * self._size)\n",
    "\n",
    "        for i in range(self._n):\n",
    "            self._d[self._size + i] = v[i]\n",
    "        for i in range(self._size - 1, 0, -1):\n",
    "            self._update(i)\n",
    "\n",
    "    def set(self, p: int, x: typing.Any) -> None:\n",
    "        assert 0 <= p < self._n\n",
    "\n",
    "        p += self._size\n",
    "        self._d[p] = x\n",
    "        for i in range(1, self._log + 1):\n",
    "            self._update(p >> i)\n",
    "\n",
    "    def get(self, p: int) -> typing.Any:\n",
    "        assert 0 <= p < self._n\n",
    "\n",
    "        return self._d[p + self._size]\n",
    "\n",
    "    def prod(self, left: int, right: int) -> typing.Any:\n",
    "        assert 0 <= left <= right <= self._n\n",
    "        sml = self._e\n",
    "        smr = self._e\n",
    "        left += self._size\n",
    "        right += self._size\n",
    "\n",
    "        while left < right:\n",
    "            if left & 1:\n",
    "                sml = self._op(sml, self._d[left])\n",
    "                left += 1\n",
    "            if right & 1:\n",
    "                right -= 1\n",
    "                smr = self._op(self._d[right], smr)\n",
    "            left >>= 1\n",
    "            right >>= 1\n",
    "\n",
    "        return self._op(sml, smr)\n",
    "\n",
    "    def all_prod(self) -> typing.Any:\n",
    "        return self._d[1]\n",
    "\n",
    "    def max_right(self, left: int,\n",
    "                  f: typing.Callable[[typing.Any], bool]) -> int:\n",
    "        assert 0 <= left <= self._n\n",
    "        assert f(self._e)\n",
    "\n",
    "        if left == self._n:\n",
    "            return self._n\n",
    "\n",
    "        left += self._size\n",
    "        sm = self._e\n",
    "\n",
    "        first = True\n",
    "        while first or (left & -left) != left:\n",
    "            first = False\n",
    "            while left % 2 == 0:\n",
    "                left >>= 1\n",
    "            if not f(self._op(sm, self._d[left])):\n",
    "                while left < self._size:\n",
    "                    left *= 2\n",
    "                    if f(self._op(sm, self._d[left])):\n",
    "                        sm = self._op(sm, self._d[left])\n",
    "                        left += 1\n",
    "                return left - self._size\n",
    "            sm = self._op(sm, self._d[left])\n",
    "            left += 1\n",
    "\n",
    "        return self._n\n",
    "\n",
    "    def min_left(self, right: int,\n",
    "                 f: typing.Callable[[typing.Any], bool]) -> int:\n",
    "        assert 0 <= right <= self._n\n",
    "        assert f(self._e)\n",
    "\n",
    "        if right == 0:\n",
    "            return 0\n",
    "\n",
    "        right += self._size\n",
    "        sm = self._e\n",
    "\n",
    "        first = True\n",
    "        while first or (right & -right) != right:\n",
    "            first = False\n",
    "            right -= 1\n",
    "            while right > 1 and right % 2:\n",
    "                right >>= 1\n",
    "            if not f(self._op(self._d[right], sm)):\n",
    "                while right < self._size:\n",
    "                    right = 2 * right + 1\n",
    "                    if f(self._op(self._d[right], sm)):\n",
    "                        sm = self._op(self._d[right], sm)\n",
    "                        right -= 1\n",
    "                return right + 1 - self._size\n",
    "            sm = self._op(self._d[right], sm)\n",
    "\n",
    "        return 0\n",
    "\n",
    "    def _update(self, k: int) -> None:\n",
    "        self._d[k] = self._op(self._d[2 * k], self._d[2 * k + 1])\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    def maximumSumQueries(self, nums1: List[int], nums2: List[int], queries: List[List[int]]) -> List[int]:\n",
    "        n, q = len(nums1), len(queries)\n",
    "        ans = [-1] * q\n",
    "        nums = sorted(zip(nums1, nums2), key=lambda x: -x[0])  # [nums1j,nums2j] 按 nums1j 降序排\n",
    "        d = {v: i for i, v in\n",
    "             enumerate(sorted(set(list(nums2) + [y for x, y in queries])))}  # 将 nums2 和 queries 中的值一起离散化\n",
    "        m = len(d)\n",
    "        seg = SegTree(lambda x, y: x if x > y else y, -1, m)\n",
    "        idx = 0\n",
    "        for i, (x, y) in sorted(enumerate(queries), key=lambda x: -x[1][0]):\n",
    "            while idx < n and nums[idx][0] >= x:\n",
    "                seg.set(d[nums[idx][1]], max(sum(nums[idx]), seg.get(d[nums[idx][1]])))\n",
    "                idx += 1\n",
    "            ans[i] = seg.prod(d[y], m)\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maximumSumQueries(self, nums1: List[int], nums2: List[int], queries: List[List[int]]) -> List[int]:\n",
    "        sorted_nums = sorted([[x, y, x + y] for x, y in zip(nums1, nums2)], key=lambda x: -x[0])\n",
    "        sorted_queries = sorted([[i, x, y] for i, (x, y) in enumerate(queries)], key=lambda x: -x[1])\n",
    "        res = [-1] * len(queries)\n",
    "        stack = []\n",
    "        j = 0\n",
    "        for i, x, y in sorted_queries:\n",
    "            while j < len(sorted_nums) and sorted_nums[j][0] >= x:\n",
    "                while stack and stack[-1][1] <= sorted_nums[j][2]:\n",
    "                    stack.pop()\n",
    "                if not stack or stack[-1][0] <= sorted_nums[j][1]:\n",
    "                    stack.append([sorted_nums[j][1], sorted_nums[j][2]])\n",
    "                j += 1\n",
    "            k = bisect_left(stack, [y, 0])\n",
    "            if k < len(stack):\n",
    "                res[i] = stack[k][1]\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class SegmentTree:\n",
    "    def __init__(self, n:int):\n",
    "        self.size = 4 * n\n",
    "        self.max = [-1] * self.size\n",
    "    \n",
    "    def add(self, o:int, l:int, r:int, index:int, val:int):\n",
    "        if l == r:\n",
    "            self.max[o] = max(self.max[o], val)\n",
    "            return\n",
    "        \n",
    "        mid = (l+r)>>1\n",
    "        if index <= mid:\n",
    "            self.add(o*2, l, mid, index, val)\n",
    "        else:\n",
    "            self.add(o*2+1, mid+1, r, index, val)\n",
    "        self.max[o] = max(self.max[o*2], self.max[o*2+1])\n",
    "        \n",
    "    def query_sum(self, o:int, l:int, r:int, L:int, R:int):\n",
    "        if r < L or l > R:\n",
    "            return 0\n",
    "        if L <= l and r <= R:\n",
    "            return self.max[o]\n",
    "        \n",
    "        s = -1\n",
    "        mid = (l+r)>>1\n",
    "        if L <= mid:\n",
    "            s = max(s, self.query_sum(o*2, l, mid, L, R))\n",
    "        if R >= mid+1:\n",
    "            s = max(s, self.query_sum(o*2+1, mid+1, r, L, R))\n",
    "        return s\n",
    "\n",
    "        \n",
    "class Solution:\n",
    "    def maximumSumQueries(self, nums1: List[int], nums2: List[int], queries: List[List[int]]) -> List[int]:\n",
    "        \n",
    "        def brute():\n",
    "            ans = []\n",
    "            for x, y in queries:\n",
    "                t = -1\n",
    "                for a, b in zip(nums1, nums2):\n",
    "                    if a >= x and b >= y:\n",
    "                        t = max(t, a + b)\n",
    "                ans.append(t)\n",
    "            return ans\n",
    "        \n",
    "        s = sorted(zip(nums1, nums2), reverse=True)\n",
    "        #print(s)\n",
    "        \n",
    "        \n",
    "        qs = sorted(enumerate(queries), key = lambda x: -x[1][0])\n",
    "        keys = set(nums2)\n",
    "        for _, y in queries:\n",
    "            keys.add(y)\n",
    "        \n",
    "        indexs = {v:k for k, v in enumerate(sorted(keys))}\n",
    "        #print(indexs)\n",
    "        N = len(indexs)\n",
    "        sg = SegmentTree(N+5)\n",
    "        j = 0\n",
    "        n = len(s)\n",
    "        ans = [-1] * len(queries)\n",
    "        for i, (x, y) in qs:\n",
    "            while j < n and s[j][0] >= x:\n",
    "                sg.add(1, 1, N, indexs[s[j][1]]+1, (s[j][0] + s[j][1]))\n",
    "                j += 1\n",
    "            \n",
    "            t = sg.query_sum(1, 1, N, indexs[y]+1, N)\n",
    "            ans[i] = t\n",
    "            \n",
    "        \n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def __init__(self):\n",
    "        self.sums=[]\n",
    "\n",
    "    @functools.lru_cache(1)\n",
    "    def query(self,q0,q1):\n",
    "        ss = q0+q1\n",
    "        for s,a in self.sums:\n",
    "            if s < ss:\n",
    "                return(-1)\n",
    "            if a >= q0 and s-a >= q1:\n",
    "                return(s)\n",
    "        return(-1)        \n",
    "\n",
    "    def maximumSumQueries(self, nums1: List[int], nums2: List[int], queries: List[List[int]]) -> List[int]:\n",
    "        self.sums = sorted([(a+b,a) for a,b in zip(nums1,nums2)],reverse=True)\n",
    "        return([self.query(q[0],q[1]) for q in queries])\n",
    "   "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    def maximumSumQueries(self, nums1: List[int], nums2: List[int], queries: List[List[int]]) -> List[int]:\n",
    "        num2_list = sorted( list( set( nums2 + [q[1] for q in queries] ) ) ) \n",
    "        hashmap = { v:k for k,v in enumerate( num2_list )  } \n",
    "\n",
    "        u = len(num2_list)\n",
    "        mx = [0] * (4 * u)\n",
    "        #直接赋值，非增加的\n",
    "        def modify(o: int, l: int, r: int, i: int, val: int) -> None:\n",
    "            if l == r:\n",
    "                mx[o] = val\n",
    "                return\n",
    "            m = (l + r) // 2\n",
    "            if i <= m: modify(o * 2, l, m, i, val)\n",
    "            else: modify(o * 2 + 1, m + 1, r, i, val)\n",
    "            mx[o] = max(mx[o * 2], mx[o * 2 + 1])\n",
    "\n",
    "        # 返回区间 [L,R] 内的最大值\n",
    "        def query(o: int, l: int, r: int, L: int, R: int) -> int:  # L 和 R 在整个递归过程中均不变，将其大写，视作常量\n",
    "            if L <= l and r <= R: return mx[o]\n",
    "            res = 0\n",
    "            m = (l + r) // 2\n",
    "            if L <= m: res = query(o * 2, l, m, L, R)\n",
    "            if R > m: res = max(res, query(o * 2 + 1, m + 1, r, L, R))\n",
    "            return res\n",
    " \n",
    "\n",
    "        n = len(nums1)\n",
    "        sorted_list = sorted( zip(nums1,nums2 ) ,key=lambda x:-x[0]) \n",
    "\n",
    "        sorted_queries  = sorted( zip(queries,range( len(queries) )) ,key=lambda x:-x[0][0])\n",
    "        list_idx = 0  \n",
    "        ans = [-1]*len(queries)\n",
    "\n",
    "        \n",
    "        # 离散化维护st表，二分查找查询下标 / 离散化线段树 / 动态开点线段树 \n",
    "        lst = [0]*len(num2_list)\n",
    "        for q,q_idx in  sorted_queries :  \n",
    "            while list_idx < n and sorted_list[list_idx][0] >= q[0]:\n",
    "                num1 = sorted_list[list_idx ][0]\n",
    "                num2 = sorted_list[list_idx ][1]\n",
    "                lst[ hashmap[num2] ]  = max( lst[ hashmap[num2] ], num1+num2 )\n",
    "                 \n",
    "                modify(1, 1, u, hashmap[num2] + 1 , lst[ hashmap[num2] ] )\n",
    "                list_idx += 1\n",
    "            ans[ q_idx ] =  query(1, 1, u, hashmap[ q[1] ] + 1 , u )\n",
    "          \n",
    "        for i in range(len(ans)):\n",
    "            if ans[i] == 0:\n",
    "                ans[i] = -1\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "\n",
    "class BinaryIndexedTree:\n",
    "    __slots__ = [\"n\", \"c\"]\n",
    "\n",
    "    def __init__(self, n: int):\n",
    "        self.n = n\n",
    "        self.c = [-1] * (n + 1)\n",
    "\n",
    "    def update(self, x: int, v: int):\n",
    "        while x <= self.n:\n",
    "            self.c[x] = max(self.c[x], v)\n",
    "            x += x & -x\n",
    "\n",
    "    def query(self, x: int) -> int:\n",
    "        mx = -1\n",
    "        while x:\n",
    "            mx = max(mx, self.c[x])\n",
    "            x -= x & -x\n",
    "        return mx\n",
    "class Solution:\n",
    "    def maximumSumQueries(self, nums1: List[int], nums2: List[int], queries: List[List[int]]) -> List[int]:\n",
    "        get = [[a, b] for a, b in zip(nums1, nums2)]\n",
    "        qu = [[a, b, i] for i, (a, b) in enumerate(queries)]\n",
    "        qu.sort(key=lambda x: x[0], reverse=True)\n",
    "        get.sort(key=lambda x: x[0], reverse=True)\n",
    "        unique_set = set()\n",
    "        for x in get:\n",
    "            unique_set.add(x[1])\n",
    "        for q in qu:\n",
    "            unique_set.add(q[1])\n",
    "        unique_list = list(unique_set)\n",
    "        unique_list.sort()\n",
    "        sz = len(unique_list)\n",
    "        mapping = {val: idx for idx, val in enumerate(unique_list)}\n",
    "        ans = [-1] * (len(qu))\n",
    "        ptr = 0\n",
    "        size = len(mapping)\n",
    "        tree = BinaryIndexedTree(size)\n",
    "        for a, b, i in qu:\n",
    "            while ptr < len(get) and get[ptr][0] >= a:\n",
    "                tree.update(sz - mapping[get[ptr][1]], get[ptr][0] + get[ptr][1])\n",
    "                ptr += 1\n",
    "            ans[i] = tree.query(size - mapping[b])\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class BinaryIndexedTree:\n",
    "    __slots__ = [\"n\", \"c\"]\n",
    "\n",
    "    def __init__(self, n: int):\n",
    "        self.n = n\n",
    "        self.c = [-1] * (n + 1)\n",
    "\n",
    "    def update(self, x: int, v: int):\n",
    "        while x <= self.n:\n",
    "            self.c[x] = max(self.c[x], v)\n",
    "            x += x & -x\n",
    "\n",
    "    def query(self, x: int) -> int:\n",
    "        mx = -1\n",
    "        while x:\n",
    "            mx = max(mx, self.c[x])\n",
    "            x -= x & -x\n",
    "        return mx\n",
    "class Solution:\n",
    "    def maximumSumQueries(self, nums1: List[int], nums2: List[int], queries: List[List[int]]) -> List[int]:\n",
    "        get = [[a, b] for a, b in zip(nums1, nums2)]\n",
    "        qu = [[a, b, i] for i, (a, b) in enumerate(queries)]\n",
    "        qu.sort(key=lambda x: x[0], reverse=True)\n",
    "        get.sort(key=lambda x: x[0], reverse=True)\n",
    "        unique_set = set()\n",
    "        for x in get:\n",
    "            unique_set.add(x[1])\n",
    "        for q in qu:\n",
    "            unique_set.add(q[1])\n",
    "        unique_list = list(unique_set)\n",
    "        unique_list.sort()\n",
    "        sz = len(unique_list)\n",
    "        mapping = {val: idx for idx, val in enumerate(unique_list)}\n",
    "        ans = [-1] * (len(qu))\n",
    "        ptr = 0\n",
    "        size = len(mapping)\n",
    "        tree = BinaryIndexedTree(size)\n",
    "        for a, b, i in qu:\n",
    "            while ptr < len(get) and get[ptr][0] >= a:\n",
    "                tree.update(sz - mapping[get[ptr][1]], get[ptr][0] + get[ptr][1])\n",
    "                ptr += 1\n",
    "            ans[i] = tree.query(size - mapping[b])\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class SegmentTreeRangeAddMax:\n",
    "    # 模板：线段树区间更新、持续增加最大值\n",
    "    def __init__(self, n):\n",
    "        self.floor = 0\n",
    "        self.height = [self.floor]*(4*n)\n",
    "        self.lazy = [self.floor]*(4*n)\n",
    "\n",
    "    @staticmethod\n",
    "    def max(a, b):\n",
    "        return a if a > b else b\n",
    "\n",
    "    def push_down(self, i):\n",
    "        # 懒标记下放，注意取最大值\n",
    "        if self.lazy[i]:\n",
    "            self.height[2 * i] = self.max(self.height[2 * i], self.lazy[i])\n",
    "            self.height[2 * i + 1] = self.max(self.height[2 * i + 1], self.lazy[i])\n",
    "            self.lazy[2 * i] = self.max(self.lazy[2 * i], self.lazy[i])\n",
    "            self.lazy[2 * i + 1] = self.max(self.lazy[2 * i + 1], self.lazy[i])\n",
    "            self.lazy[i] = self.floor\n",
    "        return\n",
    "\n",
    "    def update(self, left, right, s, t, val, i):\n",
    "        # 更新区间最大值\n",
    "        stack = [[s, t, i]]\n",
    "        while stack:\n",
    "            a, b, i = stack.pop()\n",
    "            if i >= 0:\n",
    "                if left <= a and b <= right:\n",
    "                    self.height[i] = self.max(self.height[i], val)\n",
    "                    self.lazy[i] = self.max(self.lazy[i], val)\n",
    "                    continue\n",
    "                self.push_down(i)\n",
    "                stack.append([a, b, ~i])\n",
    "                m = a + (b - a) // 2\n",
    "                if left <= m:  # 注意左右子树的边界与范围\n",
    "                    stack.append([a, m, 2 * i])\n",
    "                if right > m:\n",
    "                    stack.append([m + 1, b, 2 * i + 1])\n",
    "            else:\n",
    "                i = ~i\n",
    "                self.height[i] = self.max(self.height[2 * i], self.height[2 * i + 1])\n",
    "        return\n",
    "\n",
    "    def query(self, left, right, s, t, i):\n",
    "        # 查询区间的最大值\n",
    "        stack = [[s, t, i]]\n",
    "        highest = self.floor\n",
    "        while stack:\n",
    "            a, b, i = stack.pop()\n",
    "            if left <= a and b <= right:\n",
    "                highest = self.max(highest, self.height[i])\n",
    "                continue\n",
    "            self.push_down(i)\n",
    "            m = a + (b - a) // 2\n",
    "            if left <= m:\n",
    "                stack.append([a, m, 2*i])\n",
    "            if right > m:\n",
    "                stack.append([m+1, b, 2*i + 1])\n",
    "        return highest\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    def maximumSumQueries(self, nums1: List[int], nums2: List[int], queries: List[List[int]]) -> List[int]:\n",
    "\n",
    "        nodes = set()\n",
    "        for num in nums1:\n",
    "            nodes.add(num)\n",
    "        for num in nums2:\n",
    "            nodes.add(num)\n",
    "        for a, b in queries:\n",
    "            nodes.add(a)\n",
    "            nodes.add(b)\n",
    "\n",
    "        nodes = sorted(list(nodes))\n",
    "        dct = {num: i for i, num in enumerate(nodes)}\n",
    "\n",
    "\n",
    "        m = len(queries)\n",
    "        n = len(nodes)\n",
    "        tree = SegmentTreeRangeAddMax(n)\n",
    "\n",
    "        ind = list(range(m))\n",
    "        ind.sort(key=lambda it: -queries[it][0])\n",
    "        ans = [0]*m\n",
    "        lst = [[x, y] for x, y in zip(nums1, nums2)]\n",
    "        lst.sort(key=lambda it: -it[0])\n",
    "        j = 0\n",
    "        for i in ind:\n",
    "            x, y = queries[i]\n",
    "            while j < len(lst) and lst[j][0] >= x:\n",
    "                num1, num2 = lst[j]\n",
    "                tree.update(dct[num2], dct[num2], 0, n-1, num1+num2, 1)\n",
    "                j += 1\n",
    "            ans[i] = tree.query(dct[y], n-1, 0, n-1, 1)\n",
    "            if ans[i] == 0:\n",
    "                ans[i] = -1\n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maximumSumQueries(self, nums1: List[int], nums2: List[int], queries: List[List[int]]) -> List[int]:\n",
    "        result = []\n",
    "        max_map = {}\n",
    "\n",
    "        total_map = {}\n",
    "\n",
    "        for i in range(len(nums1)):\n",
    "            total = nums1[i] + nums2[i]\n",
    "            total_map[total] = total_map.get(total, []) + [[nums1[i], nums2[i]]]\n",
    "\n",
    "        # 排序\n",
    "        total_map_sort = sorted(total_map, reverse=True)\n",
    "        new_total_map = {k: total_map[k] for k in total_map_sort}\n",
    "\n",
    "        for qu in queries:\n",
    "            max_num = max_map.get(str(qu), None)\n",
    "            if max_num:\n",
    "                result.append(max_num)\n",
    "                continue\n",
    "            \n",
    "            max_num = self.get_max_num(new_total_map, qu)\n",
    "            result.append(max_num)\n",
    "            max_map[str(qu)] = max_num\n",
    "\n",
    "        return result\n",
    "\n",
    "    def get_max_num(self, total_map, qu):\n",
    "        n1 = qu[0]\n",
    "        n2 = qu[1]\n",
    "\n",
    "        max_n = -1\n",
    "\n",
    "        for k, v in total_map.items():\n",
    "            for sv in v:\n",
    "                if (sv[0] >= n1) and (sv[1] >= n2):\n",
    "                    return k \n",
    "\n",
    "        return max_n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "\n",
    "    def maximumSumQueries(self, nums1: List[int], nums2: List[int], queries: List[List[int]]) -> List[int]:\n",
    "        n = len(nums1)\n",
    "        a = sorted(zip(nums1, nums2), key=lambda x: x[0])\n",
    "        L, R = min(*nums2, *(y for _, y in queries)), max(*nums2, *(y for _, y in queries))\n",
    "        # L, R = 1, 10**9\n",
    "        mx = defaultdict(lambda: -1)  # [-1] * (2 << (R - L + 1).bit_length())  # 区间最大值 用defaultdict相当于动态开点了\n",
    "\n",
    "        def update(o, l, r, idx, val):  # 单点设置\n",
    "            if l == r:\n",
    "                # 相同l 取最大 或只更新前面一次\n",
    "                mx[o] = max(mx[o], val)  # if mx[o] == -1: mx[o] = val\n",
    "                return\n",
    "            m = l + r >> 1\n",
    "            if m >= idx: update(o * 2, l, m, idx, val)\n",
    "            else: update(o * 2 + 1, m + 1, r, idx, val)\n",
    "            mx[o] = max(mx[o * 2], mx[o * 2 + 1])\n",
    "\n",
    "        def query(o, l, r, si):  # 查询[si:]最大值\n",
    "            if si <= l:\n",
    "                return mx[o]\n",
    "            m = l + r >> 1\n",
    "            ans = query(o * 2 + 1, m + 1, r, si)\n",
    "            if m >= si: ans = max(ans, query(o * 2, l, m, si))\n",
    "            return ans\n",
    "\n",
    "        ans = [-1] * len(queries)\n",
    "        j = n - 1\n",
    "        for i, (x, y) in sorted(enumerate(queries), key=lambda x: -x[1][0]):\n",
    "            while j >= 0 and a[j][0] >= x:\n",
    "                update(1, L, R, a[j][1], sum(a[j]))\n",
    "                j -= 1\n",
    "            ans[i] = query(1, L, R, y)\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class BIT:\n",
    "    def __init__(self, n):\n",
    "        self.tree = [-1]*n \n",
    "        self.n = n \n",
    "    \n",
    "    def update(self, i, mx):\n",
    "        while i:\n",
    "            self.tree[i] = max(mx, self.tree[i])\n",
    "            i -= i&-i \n",
    "    \n",
    "    def query(self, i):\n",
    "        res = -1\n",
    "        while i<self.n:\n",
    "            res = max(res, self.tree[i])\n",
    "            i += i&-i \n",
    "        return res\n",
    "\n",
    "class Solution:\n",
    "    def maximumSumQueries(self, nums1: List[int], nums2: List[int], queries: List[List[int]]) -> List[int]:\n",
    "        n = len(nums1)\n",
    "        a = sorted([(x, y, x + y) for x, y in zip(nums1, nums2)])\n",
    "        qs = sorted([(x, y, i) for i, (x, y) in enumerate(queries)], reverse=True)\n",
    "        s = set(nums2) | set(y for _, y, _ in qs)\n",
    "        mp = {x: i + 1 for i, x in enumerate(sorted(s))}\n",
    "        tree = BIT(len(mp) + 1)\n",
    "        i = n - 1\n",
    "        res = [-1] * len(queries)\n",
    "        for x, y, qi in qs:\n",
    "            while i >= 0 and a[i][0] >= x:\n",
    "                tree.update(mp[a[i][1]], a[i][2])\n",
    "                i -= 1\n",
    "            res[qi] = tree.query(mp[y])\n",
    "        return res\n",
    "\n",
    "        # res = [-1] * len(queries)\n",
    "        # a = sorted(((x, y) for x, y in zip(nums1, nums2)), key=lambda p: -p[0])\n",
    "        # qs = sorted([(i, x, y) for i, (x, y) in enumerate(queries)], key=lambda x: -x[1])\n",
    "        # j = 0\n",
    "        # stk = [] #存(ay, ax + ay), ay递增，ax+ay递减\n",
    "        # for i, x, y in qs:\n",
    "        #     while j < len(a) and a[j][0] >= x:\n",
    "        #         ax, ay = a[j]\n",
    "        #         while stk and stk[-1][1] <= ax + ay:\n",
    "        #             stk.pop()\n",
    "        #         if not stk or stk[-1][0] < ay:\n",
    "        #             stk.append((ay, ax + ay))\n",
    "        #         j += 1\n",
    "        #     p = bisect_left(stk, (y,))\n",
    "        #     if p < len(stk):\n",
    "        #         res[i] = stk[p][1]\n",
    "        # return res\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maximumSumQueries(self, nums1: List[int], nums2: List[int], queries: List[List[int]]) -> List[int]:\n",
    "        nums_sum=[]\n",
    "        nums_x=[]\n",
    "        nums_y=[]\n",
    "        for i in range(len(nums1)):\n",
    "            nums_sum.append([nums1[i]+nums2[i],nums1[i],nums2[i],i])\n",
    "            nums_x.append([nums1[i],nums2[i],i])\n",
    "            nums_y.append([nums2[i],nums1[i],i])\n",
    "        nums_sum.sort(reverse=True)\n",
    "        nums_x.sort(reverse=True)\n",
    "        nums_y.sort(reverse=True)\n",
    "        \n",
    "        def get_position(nums,x):\n",
    "            left=0\n",
    "            right=len(nums)-1\n",
    "            while(left<right):\n",
    "                middle=(left+right)//2\n",
    "                if(nums[middle][0]>=x):\n",
    "                    left=middle+1\n",
    "                else:\n",
    "                    right=middle\n",
    "            return left\n",
    "\n",
    "        def check_max(nums,x,y,length):\n",
    "            ans=-1\n",
    "            for i in range(length):\n",
    "                if(nums[i][0]>=x and nums[i][1]>=y):\n",
    "                    ans=max(ans,nums[i][0]+nums[i][1])\n",
    "            return ans\n",
    "\n",
    "        # print(nums_sum)\n",
    "        def get_max(nums_sum,nums_x,nums_y,x,y):\n",
    "            position1=get_position(nums_x,x)\n",
    "            position2=get_position(nums_y,y)\n",
    "            length=len(nums_sum)\n",
    "            position_min=min(position1,position2)\n",
    "            if(position_min<=length**0.5):\n",
    "                if(position1<position2):\n",
    "                    return check_max(nums_x,x,y,position1+1)\n",
    "                else:\n",
    "                    return check_max(nums_y,y,x,position2+1)\n",
    "                \n",
    "            tmp_sum=x+y\n",
    "            for i in range(len(nums_sum)):\n",
    "                if(tmp_sum>nums_sum[i][0]):return -1\n",
    "                if(nums_sum[i][1]>=x and nums_sum[i][2]>=y):return nums_sum[i][0]\n",
    "            return -1\n",
    "        \n",
    "        ans=[-1]*len(queries)\n",
    "        for i in range(len(queries)):\n",
    "            ans[i]=get_max(nums_sum,nums_x,nums_y,queries[i][0],queries[i][1])\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maximumSumQueries(self, nums1: List[int], nums2: List[int], queries: List[List[int]]) -> List[int]:\n",
    "        arr = sorted(set(nums2 + [y for _, y in queries]))\n",
    "        mp = {v: idx + 1 for idx, v in enumerate(arr)}\n",
    "        sz = len(arr) + 1\n",
    "\n",
    "        tree = [-1] * (len(nums1) + sz + 1)\n",
    "\n",
    "        def low_bit(x: int) -> int:\n",
    "            return x & -x\n",
    "\n",
    "        def add(x: int, v: int) -> None:\n",
    "            while x < len(tree):\n",
    "                tree[x] = max(tree[x], v)\n",
    "                x += low_bit(x)\n",
    "\n",
    "        def get(x: int) -> int:\n",
    "            ans = -10 ** 9\n",
    "            while x > 0:\n",
    "                ans = max(ans, tree[x])\n",
    "                x -= low_bit(x)\n",
    "            return ans\n",
    "\n",
    "        s1 = sorted([(x, y) for x, y in zip(nums1, nums2)], key=lambda e: -e[0])\n",
    "        s2 = sorted([(x, sz - mp[y], i) for i, (x, y) in enumerate(queries)], key=lambda e: -e[0])\n",
    "\n",
    "        ans = [0] * len(queries)\n",
    "        j = 0\n",
    "\n",
    "        for i, (x, y, idx) in enumerate(s2):\n",
    "            while j < len(s1) and s1[j][0] >= x:\n",
    "                s, v = sum(s1[j]), sz - mp[s1[j][1]]\n",
    "                add(v, s)\n",
    "                j += 1\n",
    "            ans[idx] = get(y)\n",
    "\n",
    "        return ans"
   ]
  }
 ],
 "metadata": {},
 "nbformat": 4,
 "nbformat_minor": 2
}
